课程名称： 数据结构 A 适用专业年级：2010计算机\网络\软件
考生学号： 考 生 姓 名：
………………………………………………………………………………………………………
一、选择题（每小题2分，共20分）
1、将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（ ）
A.n-1 B.n C.2n-1 D.2n
2、指针p1和p2分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单循环链表，应执行的操作为（ ）
A.p1－＞next=p2－＞next;p2－＞next=p1－＞next;
B. p2－＞next=p1－＞next;p1－＞next=p2－＞next;
C. p=p2－＞next; p1－＞next=p;p2－＞next=p1－＞next;
D. p=p1－＞next; p1－＞next= p2－＞next；p2－＞next=p;
3、如果将矩阵An×n的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=((a11,a21,…,an1),( a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是（ ）
A. head (tail (head (L))) B. head (head(head(L)))
C. tail (head (tail (L))) D. head (head (tail (L)))
4、具有n个顶点、e条边的无向图的邻接矩阵中，零元素的个数为（ ）
A.e B.2e C.n2-2e D.n2-1
5、若非连通无向图G含有21条边，则G的顶点个数至少为（ ）
A．7 B．8 C．21 D．22
6、某索引顺序表共有元素395个，平均分成5块。若先对索引表采用顺序查找，再对块中元素进行顺序查找，则在等概率情况下，分块查找成功的平均查找长度是（ ）
A.43 B.79 C.198 D.200
7、要以O（nlogn）时间复杂度进行稳定的排序，可用的排序方法是（ ）
A.归并排序 B.快速排序 C.堆排序 D.冒泡排序
8、设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )
A．8 B．3 C．5 D．9
9、已知有向图G=(V，E)，其中V={V1，V2，V3，V4}，E={ A.V1,V2,V3,V4 B.V1,V3,V2,V4 C.V1,V3,V4,V2 D.V1,V2,V4,V3 10、在下图中，从顶点1出发进行深度优先遍历可得到的序列是( ) A.1 2 3 4 5 6 7 B.1 4 2 6 3 7 5 C.1 4 2 5 3 6 7 D.1 2 4 6 5 3 7 二、填空题（每空2分，共30分） 1、数据结构由数据的逻辑结构、存储结构和数据的（1）三部分组成。 2、设长度为n的链队列用只设尾指针的单循环链表表示，则出队操作的时间复杂度为（2），若用只设头指针的单循环链表表示，则出队操作的时间复杂度为（3）。 3、向一个栈顶指针为top的链栈中插入一个s指针所指结点的操作语句是（4）和（5）。 4、长度为11的有序表，采用折半查找，在等概率情况下查找成功的平均查找长度为（6）。 5、设一棵完全二叉树具有1000个结点，则此完全二叉树有(7)个叶子结点，有(8)个度为2的结点，有(9)个结点只有非空左子树，有(10)个结点只有非空右子树。 6、已知链表结点定义如下： typedef struct node{ char data［16］； struct node *next; } LinkStrNode； 如果每个字符占1个字节，指针占4个字节，则该链表的存储密度是（11）。 7、使用一个100个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队空和队满，约定队头指针front等于队尾指针rear时表示队空。若为front=8，rear=7，则队列中的元素个数为（12）。 8、用5个权值{3, 2，4，5，1}构造的哈夫曼(Huffman)树的带权路径长度是（13）。 9、快速排序、简单选择排序和直接插入排序三种排序方法中，当待排关键字序列基本有序时，运行效率最高的是（14），比较次数与待排记录初始状态无关的是（15）。 三、分析题（共26分） 1(8分)已知一个森林的前序遍历序列为CBADHEGF，后序遍历序列为ABCDEFGH，画出森林。 2(8分)已知待排记录的关键字序列为{25，96，11，63，57，78，44}，请回答下列问题： (1)写出堆排序的初始堆（大根堆）关键字序列； 写出堆排序1趟以后（交换与调整之后）的关键字序列； (2)写出快速排序1趟以后的关键字序列； 写出快速排序2趟以后的关键字序列。 3(5分)假设具有n个结点的完全二叉树顺序存储在向量BT[1.. n]中，阅读下列算法，并回答问题： 若向量BT为： 画出执行函数f（BT,7,1）的返回结果，简述函数f的功能。 BinTree f(DataType BT[],int n,int i) { BinTree p; if (i＞n) return NULL; p=（BinTNode*）malloc(sizeof(BinTNode)); p－＞data=BT[i]; p－＞lchild=f(BT,n,i*2); p－＞rchild=f(BT,n,i*2+1); return p; } 4(5分)如图所示，在n×n矩阵A中，所有下标值满足关系式i+j＜n+l的元素aij的值均为0，现将A中其它元素按行优先顺序依次存储到长度为n(n+1)/2的一维数组sa中，其中元素a1，n存储在sa［0］。 (1)设n=10，元素a4，9存储在sa［p］，写出下标p的值； (2)设元素ai，j存储在sa［k］中，写出由i,j和n计算k的一般公式。 四、程序设计题（共24分） 1(10分)将二叉树bt中每一个结点的左右子树互换的C语言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。 typedef struct node{ int data; struct node *lchild, *rchild; }btnode; void EXCHANGE(btnode *bt) { btnode *p, *q; if (bt) { ADDQ(Q,bt); while(!EMPTY(Q)) { p=DELQ(Q); q=(1)___; p->rchild=(2)___; (3)___=q; if(p->lchild) (4)___; if(p->rchild) (5)___; } } } 2(6分)已知有向图的邻接表和邻接矩阵定义如下： ﹟define MaxNum 50 ∥图的最大顶点数 typedef struct node { int adjvex; ∥邻接点域 struct node *next; ∥链指针域 } EdgeNode; ∥边表结点结构 typedef struct{ char vertex； ∥顶点域 EdgeNode *firstedge; ∥边表头指针 } VertexNode; ∥顶点表结点结构 typedef struct { VertexNode adjlist [MaxNum]; ∥邻接表 int n,e; ∥图中当前顶点数和边数 } ALGraph; ∥邻接表描述的图 typedef struct{ char vertex[MaxNum]; ∥顶点表 int adjmatrix [MaxNum][MaxNum]; ∥邻接矩阵 int n,e; ∥图中当前顶点数和边数 } AMGraph; ∥邻接矩阵描述的图 下列算法是将邻接表描述的图G1改为邻接矩阵描述的图G2，在空白处填上适当内容使算法完整： void f（ALGraph G1,AMGraph *G2） { int i, j; EdgeNode *p; G2－＞n=G1.n; G2－＞e= (1) ; for (i=0; i＜G1.n; i++) { G2－＞vertex[i]= (2) ; p=G1.adjlist[i].firstedge; for (j=0; j＜G1.n; j++） G2－＞adjmatrix[i][j]=0; while (p) { G2－＞adjmatrix[i][p－＞adjvex]=1; (3) ; } } } 3(8分)假设线性表采用顺序存储结构，其类型定义如下： #define ListSize 100 typedef struct { int data［ListSize］; int length; } SeqList; 编写算法，将顺序表L中所有值为奇数的元素调整到表的前端。 请先用简短的中文说明你的算法思路，然后编程：void f (SeqList *L)下载本文
1 2 3 4 5 6 7A B C D E F G
