DOC《全真试题（二）》

全真试题

(二) 本试卷分两部分,第一部分为选择题,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. 不可能生成右图所示二叉排序树的关键字序列是( ) 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趟: 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;

//邻接点域 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,请填入合适的内容,使其成为........