全真试题(二) 本试卷分两部分,第一部分为选择题,1页至2页,第二部分为非选择题,3页至10页,共10页;选择 题30分,非选择题70分,满分100分。考试时间150分钟。 第一部分选择题(共30分) 单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个选项中只有一个是符合 题目要求的,请将其代码填在题后的括号内。错选或未选均无分。 1、若结点的存储地址与其关键字之间存在的某种映射关系,则称这种存储结构为() A.顺序存储结构 B链式存储结构 C.索引存储结构 D.散列存储结构 2.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素,元素的移动次数为 B n-1 C 3.对于只在表的首尾两端进行插入操作的线性表,宜采用的存储结构为( A.顺序表 B用头指针表示的单循环链表 C.用尾指针表示的单循环链表D单链表 4.若进栈序列为a,b,c,则通过入出栈操作可能得到的a,b,c的不同排列个数为() B.5 D.7 5.为查找某一特定单词在文本中出现的位置,可应用的串运算是 A.插入B删除C串联接D子串定位 6.已知函数Sub(sij)的功能是返回串s中从第i个字符起长度为j的子串,函数 Scopy(st)的功能为复制串 t到s。若字符串S=“ SCIENCESTUDY”,则调用函数 Scopy(PSub(S,1,7)后得到() A.P=“ SCIENCE”BP=“ STUDY”C.S=“ SCIENCE”DS=“ STUDY” 7.三维数组h[4[5J6按行优先存储方法存储在内存中,若每个元素占2个存储单元,且数组中第一个元 素的存储地址为120,则元素A[3]4[5]的存储地址为() A.356 B.385 C.360D.362 8.如右图所示广义表是一种() A线性表B纯表C结点共享表D递归表 9.下列陈述中正确的是() A.二叉树是度为2的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为2的结点 D二叉树中最多只有两棵子树,并且有左右之分 10.n个顶点的有向完全图中含有有向边的数目最多为() B Cn(n-1)/2 D n(n-1) 11.已知一个有向图如右所示 则从顶点a出发进行深度优先遍历, 不可能得到的DFS序列为() Aadbefc Badcefb Cadc bfe D. b 12.在最好和最坏情况下的时间复杂度均为O( nlogn)且稳定的排序方法是() A.快速排序B堆排序C归并排序D基数排序 13.不可能生成右图所示二叉排序树的关键字序列是()
全真试题（二） 本试卷分两部分，第一部分为选择题，1 页至 2 页，第二部分为非选择题，3 页至 10 页，共 10 页；选择 题 30 分，非选择题 70 分，满分 100 分。考试时间 150 分钟。 第一部分 选择题（共 30 分） 一、单项选择题（本大题共 15 小题，每小题 2 分，共 30 分）在每小题列出的四个选项中只有一个是符合 题目要求的，请将其代码填在题后的括号内。错选或未选均无分。 1、若结点的存储地址与其关键字之间存在的某种映射关系，则称这种存储结构为（ ） A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构 2. 在长度为 n 的顺序表的第 i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数为（ ） A.n-i+1 B.n-i C.i D.i-1 3. 对于只在表的首.尾两端进行插入操作的线性表，宜采用的存储结构为（ ） A.顺序表 B.用头指针表示的单循环链表 C.用尾指针表示的单循环链表 D.单链表 4. 若进栈序列为 a，b，c，则通过入出栈操作可能得到的 a，b，c 的不同排列个数为（ ） A.4 B.5 C.6 D.7 5. 为查找某一特定单词在文本中出现的位置，可应用的串运算是（ ） A.插入 B.删除 C.串联接 D.子串定位 6. 已知函数 Sub(s,i,j)的功能是返回串 s 中从第 i 个字符起长度为 j 的子串，函数 Scopy(s,t)的功能为复制串 t 到 s。若字符串 S=“SCIENCESTUDY”，则调用函数 Scopy(P,Sub(S,1,7)后得到（ ） A.P=“SCIENCE” B.P=“STUDY” C.S=“SCIENCE ” D.S=“STUDY” 7. 三维数组 h[4][5][6]按行优先存储方法存储在内存中，若每个元素占 2 个存储单元，且数组中第一个元 素的存储地址为 120，则元素 A[3][4][5]的存储地址为（ ） A.356 B.385 C.360 D.362 8. 如右图所示广义表是一种（ ） A.线性表 B.纯表 C.结点共享表 D.递归表 9. 下列陈述中正确的是（ ） A.二叉树是度为 2 的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为 2 的结点 D.二叉树中最多只有两棵子树，并且有左右之分 10. n 个顶点的有向完全图中含有有向边的数目最多为（ ） A.n-1 B.n C.n(n-1)/2 D.n(n-1) 11. 已知一个有向图如右所示， 则从顶点 a 出发进行深度优先遍历， 不可能得到的 DFS 序列为（ ） A.a d b e f c B.a d c e f b C.a d c b f e D.a d e f c b 12. 在最好和最坏情况下的时间复杂度均为 O(nlogn)且稳定的排序方法是（ ） A.快速排序 B.堆排序 C.归并排序 D.基数排序 13. 不可能生成右图所示二叉排序树的关键字序列是（ ） p b a d c e f 1 2 3 5 4
A.45312B42531C.45213D42315 14.AVL树是一种平衡的二叉排序树,树中任一结点的( A.左右子树的高度均相同 B左右子树高度差的绝对值不超过1 C左子树的高度均大于右子树的高度D左子树的高度均小于右子树的高度 15.在ⅤSAM文件的控制区间中,记录的存储方式为() A.无序顺序B有序顺序C.无序链接D.有序链接 第二部分非选择题(共70分) 二填空题(本大题共10小题,每小题2分,若有两个空格,每个空格1分,共20分)不写解答过程, 将正确的答案写在每小题的空格内。错填或不填均无分。 16.若一个算法中的语句频度之和为T(n)=3720n+4 nlogn,则算法的时间复杂度为 17.。在如图所示的链表中,若在指针p所指的结点之后插入数据域值相继为a和b的两个结点,则可用下 列两个语句实现该操作,它们依次是 b 题17图 18.假设以S和X分别表示进栈和退栈操作,则对输入序列ab,cd,e进行一系列栈操作 SSXSXSSXXX之 得到的输出序列为 19.串S=“ I am a worker”的长度是 20.假设一个10阶的下三角矩阵A按列优先顺序压缩存储在一维数组C中,则C数组的大小应 为 21.在n个结点的线索二叉链表中,有 个线索指针 22.若采用邻接矩阵结构存储具有n个顶点的图,则对该图进行广度优先遍历的算法时间复杂度 为 23.对关键字序列(52,80,63,44,48,91)进行一趟快速排序之后得到的结果为 24.由10000个结点构成的二叉排序树,在等概率查找的假设下,查找成功时的平均查找长度的最大值可 能达到 25.若要找出所有工资低于1500元,职称是副教授,及所有工资低于2000元,职称是教授的记录,则查 询条件是 三解答题(本大题共4小题,每小题5分,共20分) 26.已知一个6行5列的稀疏矩阵中非零元的值分别为:-90,41,-76,28,-54,65和-8,它们在矩阵中 的列号依次为:1,4,5,1,2,4和5。当以带行表的三元组表作存储结构时,其行表 RowTab中的值依 次为0,0,2,2,3和5。请写出该稀疏矩阵(注:矩阵元素的行列下标均从1开始) 27.已知树T的先序遍历序列为 ABCDEFGHUKL后序遍历序列为 CBEFDJIKLHGA。请画出树T。 28.对关键字序列(72,87,61,23,94,16,05,58)进行堆排序,使之按关键字递减次序排列。请写 出排序过程中得到的初始堆和前三趟的序列状态 初始堆 第1趟: 第2趟: 第3趟
A.4 5 3 1 2 B.4 2 5 3 1 C.4 5 2 1 3 D.4 2 3 1 5 14. AVL 树是一种平衡的二叉排序树，树中任一结点的（ ） A.左.右子树的高度均相同 B.左.右子树高度差的绝对值不超过 1 C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度 15. 在 VSAM 文件的控制区间中，记录的存储方式为（ ） A.无序顺序 B.有序顺序 C.无序链接 D.有序链接 第二部分 非选择题（共 70 分） 二.填空题（本大题共 10 小题，每小题 2 分，若有两个空格，每个空格 1 分，共 20 分）不写解答过程， 将正确的答案写在每小题的空格内。错填或不填均无分。 16. 若一个算法中的语句频度之和为 T(n)=3720n+4nlogn，则算法的时间复杂度为 。 17. 在如图所示的链表中，若在指针 p 所指的结点之后插入数据域值相继为 a 和 b 的两个结点，则可用下 列两个语句实现该操作，它们依次是 和 。 题 17 图 18. 假设以 S 和 X 分别表示进栈和退栈操作，则对输入序列 a,b,c,d,e 进行一系列栈操作 SSXSXSSXXX 之 后，得到的输出序列为 。 19. 串 S=“I am a worker”的长度是 。 20. 假设一个 10 阶的下三角矩阵 A 按列优先顺序压缩存储在一维数组 C 中，则 C 数组的大小应 为 。 21. 在 n 个结点的线索二叉链表中，有 个线索指针。 22. 若采用邻接矩阵结构存储具有 n 个顶点的图，则对该图进行广度优先遍历的算法时间复杂度 为 。 23. 对关键字序列（52，80，63，44，48，91）进行一趟快速排序之后得到的结果为 。 24. 由 10000 个结点构成的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度的最大值可 能达到 。 25. 若要找出所有工资低于 1500 元，职称是副教授，及所有工资低于 2000 元，职称是教授的记录，则查 询条件是 。 三.解答题（本大题共 4 小题，每小题 5 分，共 20 分） 26. 已知一个 6 行 5 列的稀疏矩阵中非零元的值分别为：-90，41，-76，28，-54，65 和-8，它们在矩阵中 的列号依次为：1，4，5，1，2，4 和 5。当以带行表的三元组表作存储结构时，其行表 RowTab 中的值依 次为 0，0，2，2，3 和 5。请写出该稀疏矩阵（注：矩阵元素的行列下标均从 1 开始）。 27. 已知树 T 的先序遍历序列为 ABCDEFGHIJKL 后序遍历序列为 CBEFDJIKLHGA。请画出树 T。 28. 对关键字序列（72，87，61，23，94，16，05，58）进行堆排序，使之按关键字递减次序排列。请写 出排序过程中得到的初始堆和前三趟的序列状态。 初始堆： 第 1 趟： 第 2 趟： 第 3 趟： a b p s Λ
29.在关键字序列(07,12,15,18,27,32,41,92)中用二分查找法查找和给定值92相等的关键字, 请写出查找过程中依次和给定值“92”比较的关键字 四算法阅读题(本大题共4小题,每小题5分,共20分) 30.以下函数中,h是带头结点的双向循环链表的头指针。 (1)说明程序的功能 (2)当链表中结点数分别为1和6(不包括头结点)时,请写出程序中 while循环体的执行次数 int f( DlistNode *h) DlistNode*p, int F=l prior while(p I=g & p->prior I =q) if(p->data==q->data p=p->next qq->prIc else 1=0 return J 31.设栈S=(1,2,3,4,5,6,7),其中7为栈顶元素。请写出调用algo(&S)后栈S的状态。 void algo(Stack*S inti=o- Queue Q; Stack T Init Queue(&Q); InitStack(&T) while(STack Empty(s)) if(i=l i)I=0) Push(&T, Pop(&S)); else EnQueue(&Q, Pop(&s)) while(! Queue Empty(Q) Push(&s, De Queue( &Q) while(I Empty(D) Push(&s, Pop(&T)) 32.已知带权图的邻接矩阵表示和邻接表表示的形式说明分别如下: # define maxNum50/图的最大顶点数 # define INfINity INT mAX∥ NT MAX为最大一整数,表示∞ typedef struce har vexs( MaxnNum],∥字符类型的顶点表 int edges[ MaxNum] MaxNum],∥权值为整型的邻接矩阵 intn,e,∥图中当前的顶点数和边数 MGraph;∥邻接矩阵结构描述
29. 在关键字序列（07，12，15，18，27，32，41，92）中用二分查找法查找和给定值 92 相等的关键字， 请写出查找过程中依次和给定值“92”比较的关键字。 四.算法阅读题（本大题共 4 小题，每小题 5 分，共 20 分） 30. 以下函数中，h 是带头结点的双向循环链表的头指针。 （1）说明程序的功能 ； （2）当链表中结点数分别为 1 和 6（不包括头结点）时，请写出程序中 while 循环体的执行次数。 int f (DlistNode * h) { DlistNode * p, * q; int j=1; p=h-＞nest; q=h-＞prior; while(p != q && p-＞prior != q) if (p-＞data==q-＞data) { p=p-＞next; q=q-＞prior; } else j =0; return j; } 31. 设栈 S=（1，2，3，4，5，6，7），其中 7 为栈顶元素。请写出调用 algo（&S）后栈 S 的状态。 void algo (Stack *S) { int i =0; Queue Q; Stack T; InitQueue(&Q); InitStack(&T); while (!StackEmpty(S)) { if ((i=!i) !=0) Push(&T,Pop(&S)); else EnQueue(&Q, Pop(&S)); } while (! Queue Empty(Q)) Push(&S,DeQueue(&Q)); while (!StackEmpty(T)) Push (&S,Pop(&T)); } 32. 已知带权图的邻接矩阵表示和邻接表表示的形式说明分别如下： # define MaxNum 50 //图的最大顶点数 # define INFINITY INT_MAX //INT_MAX 为最大一整数，表示∞ typedef struce{ char vexs[MaxnNum]; //字符类型的顶点表 int edges[MaxNum][MaxNum]; //权值为整型的邻接矩阵 int n, e; //图中当前的顶点数和边数 } MGraph; //邻接矩阵结构描述
typedef struct node int adjvex,∥邻接点域 ∥边的权值 struct node*next,∥/指针域 } EdgeNode*next;,∥边表结点结构描述 typedef struct( char vertex;/顶点域 Edgenode=* firstedge,∥边表头指针 Vertex Node,∥顶点表结点结构描述 typedef struct VertexNode adjlist[[ MaxNum]∥邻接表 intn,e;∥/图中当前的顶点数和边数 ALGraph,∥邻接表结构描述 下列算法是根据一个带权图的邻接矩阵存储结构G1建立该图的邻接表存储结构G2,请填入合适的内容 使其成为一个完整的算法。 void convert(MGraph*Gl, ALGraph*G2) Int 1, EdgeNode*p: G2->n=GI->n: G2->e=G1->e for(i=0; in; 1++) G2->adjlist[i vertex=Gl->vexs] G2->adjlist[i firstedge= for(i=0; in; 1++) for (=0; jn;j++) if(G1->deges[JD]INFINITY { p=(Edge Node ")malloc(sizeof(EdgeNode)) p- p->adjvex=j p->next=G2->adjlist(i]. firstedge; 33阅读下列算法,并回答下列问题: (1)该算法采用何种策略进行排序? (2)算法中R[n+1的作用是什么? typedef struct i Key Type key info Type otherinfo i node Type typedef node Type sqlist MAXLENI
typedef struct node{ int adjvex; //邻接点域 int weight; //边的权值 struct node *next; //链指针域 } EdgeNode *next; //边表结点结构描述 typedef struct{ char vertex; //顶点域 EdgeNode* firstedge; //边表头指针 } VertexNode; //顶点表结点结构描述 typedef struct{ VertexNode adjlist[MaxNum]; //邻接表 int n, e; //图中当前的顶点数和边数 } ALGraph; //邻接表结构描述 下列算法是根据一个带权图的邻接矩阵存储结构 G1 建立该图的邻接表存储结构 G2，请填入合适的内容， 使其成为一个完整的算法。 void convertM(MGraph * G1, ALGraph *G2) { int i, j; EdgeNode *p; G2-＞n=G1-＞n; G2-＞e=G1-＞e; for (i=0; i＜G1-＞n; i++ ) { G2-＞adjlist[i].vertex=G1-＞vexs[i]; G2-＞adjlist[i].firstedge= (1) ; } for (i=0; i＜G1-＞n; i++ ) for (j=0; j＜G1-＞n; j++ ) if (G1-＞deges[i][j]＜INFINITY { p=(Edge Node *)malloc (sizeof (EdgeNode)); p-＞weight= (2) ; p-＞adjvex=j; p-＞next=G2-＞adjlist[i].firstedge; (3) ; } } 33.阅读下列算法，并回答下列问题： （1）该算法采用何种策略进行排序？ （2）算法中 R[n+1]的作用是什么？ typedef struct { KeyType key; infoType otherinfo; }nodeType; typedef nodeType SqList [MAXLEN];
void sort(SqlistR, int n ∥n小于 MAXLEN-1 int k or(k=n-1;k>=1;k-) if(r[k]. key>R(k+l]. key) R[n+1=R[k] for(i=k+1; R[i]. key <Rn+l].key; i++) R[]=R R[i-]=R[n+1l; 三算法设计题(本题共10分) 34.假设二叉树T采用如下定义的存储结构 typedef struct nodet Date Type data, Struct node* Child, rchild, 'parent i BIntRee 其中,结点的 Child域和 rchild域已分别填有指向其左右孩子结点的指针,而 parent域中的值为空指针(拟 作为指向双亲结点的指针域)。请编写一个递归算法,将该存储结构中各结点的 parent域的值修改成指向 其双亲结点的指针
void sort (SqList R, int n) { // n 小于 MAXLEN-1 int k, i; for (k=n-1; k＞=1; k--) if (R[k].key＞R[k+1].key) { R[n+1]=R[k]; for (i=k+1; R[i].key＜R[n+1].key; i++) R[i-1]=R[i]; R[i-1]=R[n+1]; } } 三.算法设计题（本题共 10 分） 34. 假设二叉树 T 采用如下定义的存储结构： typedef struct node{ DateType data; Struct node * lchild, *rchild, *parent; } PBinTree; 其中，结点的 lchild 域和 rchild 域已分别填有指向其左.右孩子结点的指针，而 parent 域中的值为空指针（拟 作为指向双亲结点的指针域）。请编写一个递归算法，将该存储结构中各结点的 parent 域的值修改成指向 其双亲结点的指针