一、( 共34分，每题2分)单项选择题
1、在非空循环双链表中q所指的结点前插入一个由p所指结点的过程依次为：p->next=q；p->prior=q->prior；q->prior=p；（ ）；
A．q->next=p B．q->prior->next=p C．p->prior->next=p D．p->next->prior=p E．以上答案都不对 2、已知有向图G=(V,E)，其中V={v1,v2,v3,v4,v5,v6,v7}，E={ 3、每个存储结点只含有一个数据元素，存储结点均匀地存放在连续的存储空间，使用函数值对应结点的存储位置，该存储方式是（ ）存储方式 A． 顺序 B．链接 C．索引 D．散列 E．以上答案都不对 4、对于单链表形式的队列，队空的条件是（ ） A．F＝R＝nil B．F＝R C．F≠nil且R＝nil D．R－F＝1 E．以上答案都不对 5、采用邻接表存储的图的深度优先遍历算法类似于树的（ ）。 A． 中根遍历 B．先根遍历 C．后根遍历 D．按层次遍历 E．以上答案都不对 6、对于序列(49,38,65,97,76,13,27,50)按由小到大进行排序，（ ）是初始步长d=4的希尔排序法第一趟的结果。 A． 49,76,65,13,27,50,97,38 B． 13,27,38,49,50,65,76,97 C． 97,76,65,50,49,38,27,13 D． 49,13,27,50,76,38,65,97 E．以上答案都不对 7、在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（ ）。 2 A．O（n） B．O（1） C．O（n） D．O（log2n） E．以上答案都不对 8、设n阶方阵是一个上三角矩阵，则需存储的元素个数为（ ）。 A．n B．n*n C．n*n/2 D．n(n+1)/2 E．以上答案都不对 9、树中所有结点的度等于所有结点数加（ ）。 A．0 B．1 C．－1 D．2 E．以上答案都不对 10、如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（ ）方法最快。 A．起泡排序 B．快速排序 C．堆排序 D．直接选择排序 E．以上答案都不对 11、循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别为front和rear，则当前元素个数为（ ）。 A．(rear-front+m) mod m B．rear-front+1 C．rear-front-1 D．rear-front E．以上答案都不对 12、若线性表最常用的运算是查找第i个元素及其前驱的值，则采用（ ）存储方式节省时间。 A．单链表 B．双链表 C．单循环连表 D．顺序表 E．以上答案都不对 13、树最适合用来表示（ ） A．有序数据元素 B．无序数据元素 C．元素之间无联系的数据 D．元素之间有分支层次关系 E．以上答案都不对 14、多关键字文件是指（ ） A．有多个主关键字 B．有多个次关键字 C．有一个主关键字多个次关键字 D．有多个主关键字和多个次关键字 E．以上答案都不对 15、有m个叶子结点的赫夫曼树所具有的结点数为（ ） A．m B．m+1 C．2m D．2m-1 E．以上答案都不对 16、有n个结点的有向完全图的边数为（ ） A．n*n B．2n C．n(n-1) D．2n(n+1) E．以上答案都不对 17、判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（ ）。 A．求关键路径的方法 B．求最短路径的DIJKSTRA方法 C．深度优先遍历算法 D．广度优先遍历算法 E．以上答案都不对 二、（共30分，每空2分）填空题 1、在进行直接插入排序时, 其数据比较次数与数据的初始排列（ ）关；而在进行直接选择排序时，其数据比较次数与数据的初始排列（ ）关。 2、对于一个具有N个结点和E条边的无向图，若采用邻接表表示，则顶点表的大小为（ ），所有边链表中边结点的总数为（ ）。 3、数据的逻辑结构可形式地用一个二元组B＝(K，R)来表示，其中K是( )，R是( )。 4、链表适用于（ ）查找。 5、通常程序在调用另一个程序时，都需要使用一个（ ）来保存被调用程度内分配的局部变量、形式参数的存储空间以及返回地址。 6、对一般树和森林的后序遍历序列的次序与对应的二叉树的（ ）遍历次序相同。 7、前序为abc且后序为cba的二叉树共有（ ）棵。 8、设广义表C=((x,(a,b)),((x,(a,b)),y)),则C的长度为（ ），深度为（ ）。 9、快速排序的平均时间复杂度是（ ）。 10、有n结点的二叉链表中，空指针域有（ ）个；利用这些空指针域，存放指向结点在中序次序下的前趋或后继的指针，这种附加的指针称为（ ）。 三：（共11分,每题1分）判断题(下列各题，你认为正确的，请打“ √”，错的打“×”) 1、线性表采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。（ ） 2、只允许最下面的二层结点的度数小于2的二叉树是完全二叉树。（ ） 3、二叉排序树或者是一颗空二叉树，或者是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值；若它的右子树非空，则根结点的值小于其左孩子的值。( ) 4、凡是递归定义的数据结构都可以用递归算法来实现它的操作。 （ ） 5、当向一个小根堆（最小堆）中插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。（ ） 6、对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（n）。（ ） 7、在散列法中采取开散列（链地址）法来解决冲突时，其装载因子的取值一定在（0，1）之间。（ ） 8、执行某个排序算法过程中，最初相邻的结点排序后也相邻，则算法是稳定的。( ) 9、对具有n个顶点的连通图进行深度优先遍历，所得定点序列是唯一的。( ) 10、由于在线性表的链接存储表示中增加了指针字段，所以它比线性表的顺序表示更浪费空间。( ) 11、无向图的邻接矩阵一定是对称的，有向图的邻接矩阵则一定是非对称矩阵。( ) 四、（10分）已知待排序文件各记录的排序码顺序如下 72 73 71 23 94 16 05 68 请列出快速排序过程中每一趟的排序结果。 五、（10分）对于一个n×n的矩阵A的任一元素A[i][j]，按行存储时和按列存储时的地址之差是多少。（若设两种存储的开始存储地址LOC（0，0）及元素所占存储单元数d相同） 六、（10分）给定字母a,b,c,d,e的使用频率为0.09,0.17,0.2,0.23,0.31。设计以该权值为基础的赫夫曼树，并给出赫夫曼编码。 七、（15分）已知num为无符号十进制整数，请写一非递归算法，该算法输出num对应的r进制的各位数字。要求算法中用到的栈采用线性链表存储结构（1 一、( 共34分，每题2分)单项选择题 1、C 2、A 3、D 4、A 5、B 6、D 7、B 8、D 9、C 10、D 11、A 12、D 13、D 14、C 15、D 16、C 17、C 二、（共30分，每空2分）填空题 1、答：有 、无 2、答：N、2E 3、答：结点的有穷集合、K上关系的有穷集合 4、答：顺序 5、答：栈 6、答：中 7、答：4 8、答：2, 4 9、答：O(nlog2n) 10、答：n+1, 线索 三：（共11分，每题1分）判断题 1、√ 2、× 3、× 4、√ 5、√ 6、√ 7、× 8、× 9、× 10、× 11、× 四、（10分）各趟结果如下： [68 05 71 23 16] 72 [94 73] [16 05 23] 68 [71] 72 [94 73] [05] 16 [23] 68 [71] 72 [94 73] 05 16 [23] 68 [71] 72 [94 73] 05 16 23 68 71 72 [94 73] 05 16 23 68 71 72 [73] 94 05 16 23 68 71 72 73 94 五、（10分）按行存储时与按列存储时，计算A[i][j]地址的公式分别为 LOC（i，j）=LOC（0，0）+（I*n＋j）*d 及 LOC'（i，j）=LOC（0，0）＋（j*n＋i）*d 两者相减，得 LOC（i，j）－LOC'（i，j）=LOC（0，0）＋（i*n＋j）*d－LOC（0，0）－（j*n＋i）*d =（i－j）*n*d＋（j－i）*d或： =（i－j）*（n－1）*d 六、（10分） c d e c a b c(00) d(01) a(100) b(101) e(11) 七、（15分）解： typedef struct node{ int data; struct node *next; }link; void trans(int num,int r) { link *head=NULL,*s; int n; while (num>0){ n=num%r; s=(link *)malloc(sizeof(link)); s->data=n; s->next=head; head=s; num=num/r; } printf(“输出r进制的各位数字：”)； s=head; while (s!=NULL){ printf(“%d”,s->data); s=s->next; } } 八、（15分）解： int GetLeaves( BinTree root) { //求叶结点总数 static int leaf=0;//此l用于记叶结点数，注意用静态变量 if(root) { //递归计算叶结点数 if(!(root->lchild||root->rchild)) leaf++; //如果该结点无左右孩子，则叶子数加1 GetLeaves(root->lchild);//算左子数的叶结点数 GetLeaves(root->rchild);//算右子树的叶结点数 } return leaf; //返回结果 } 九、（15分）解： Void split(ListNode *L, ListNode *&A, ListNode *&B) { ListNode *p=L->next; A=(ListNode *)malloc(sizeof(ListNode ));A->next=A; B=(ListNode *)malloc(sizeof(ListNode ));B->next=B; while (p!=L){ if (p->data%2==1){ q=p; p=p->next; q->next=A->next; A->next=q; } else { q=p; p=p->next; q->next=B->next; B->next=q; } } } 因篇幅问题不能全部显示，请点此查看更多更全内容