数据结构自考本科试题

链式存储结构的特点是借助_指示数据元素地址的指针______来表示数据元素之间的逻辑关系。数据的存储结构是其逻辑结构在计算机中的___存放形式________。

《数据结构》试题一、选择题（每小题2分，共30分）1． 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。A、单链表 B、双链表 C、单向循环 D、顺序表2． 串是任意有限个（ ）A、符号构成的序列 B、符号构成的集合C、字符构成的序列 D、字符构成的集合3． 设矩阵A（aij ，l≤i,j≤ 10）的元素满足：aij≠0(i≥j, l≤i, j≤ 10)aij=0 (i。( )i6．对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。( )7．“顺序查找法”是指在顺序表上进行查找的方法。（ ）8．向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（）9．键值序列{A，C，D，E，F，E，F}是一个堆。10．二路归并时，被归并的两个子序列中的关键字个数一定要相等。（） 三、填空题（每小题2分，共20分）1．在带有头结点的单链表L中，若要删除第一个结点，则需执行下列三条语句：＿＿＿＿＿＿＿＿；L->next=U->next；free(U)；2．有一个长度为20的有序表采用二分查找方法进行查找，共有＿＿＿＿＿＿个元素的查找长度为3。3．采用冒泡排序对有n个记录的表A按键值递增排序，若L的初始状态是按键值递增，则排序过程中记录的比较次数为＿＿＿＿＿。若A的初始状态为递减排列，则记录的交换次数为＿＿＿＿＿＿＿。4．在无头结点的双链表中，指针P所指结点是第一个结点的条件是＿＿＿＿＿＿。5．G为无向图，如果从G的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是＿＿＿＿＿图。6．如果一个有向图中没有＿＿＿＿＿＿，则该图的全部顶点可能排成一个拓扑序列。7．深度为8（根的层次号为1）的满二叉树有＿＿＿＿＿＿个叶子结点。 8．将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X，其双亲PARENT（X）的编号为＿＿＿＿＿＿＿。9．设某闭散列表HT未满，散列函数H（KEY）为键值第一字母在字母表中的序号，处理冲突方法为线性探测法，请在下列算法划线处填上适当内容，以实现按键值第一字母的顺序输出闭散列表中所有键值的算法。void printword(keytype HT[m]) { for(i=1;i<=26;i++) { j=i; while(____________________) { if (____________________) printf(“datatype”,HT[j]); j=(j+1)% m; } } }10．设有一个链队，结点结构为data|next，front为队头指针，rear为队尾指针，当执行入队操作时需执行下列语句：malloc(p)；p->data=x; p->next=NULL；＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿；＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿； 四、简答题：（每小题4分，共20分）1. 对于一个有10000个结点的二叉树，树叶最多有多少个？最少有多少个？2. 已知一棵二叉树的中序序列和后序序列分别为： DBGEACHF和DGEBHFCA，则该二叉树的前序序列是什么？3. 设有1000个无序的元素，需排出前10个最大（小）的元素，你认为采用哪种排序方法最快？为什么？4. 在KMP算法中，已知模式串为ADABCADADA ，请写出模式串的next[j]函数值。5. 中序遍历的递归算法平均空间复杂度为多少？ 五、 算法设计题（每小题10分，共20分）1. 试编写一个算法，判断一给定的整型数组a[n]是不是一个堆。2. 一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积。试写一高效算法，求二叉树的繁茂度。参考答案一、选择题1、D 2、C 3、D 4、C 5、D 6、D 7、A 8、B 9、D 10、C 11、D 12、C 13、B14、C15、D二、判断题 1. √ 2. × 3. √ 4. √ 5. × 6. × 7. × 8. √ 9. √ 10. × 三、填空题1．U=L - > next2．4。3．n-1、n(n-1)/2。4．p - > prior = NULL。5．连通6．回路或环7．28-1 = 27 = 1288．249．HT[j]!=NULL或HT[j]不为空、H(HT[j])=I10．rear - > next = p、rear = p四、简答题：1. 答： 最多是完全二叉树的形态，即5000个叶子；最少是单支树的形态，即1个叶子。2.答：是：ABDEGCFH3. 答：用锦标赛排序或堆排序很合适，因为不必等全部元素排完就能得到所需结果，时间效率为O(nlog2n)； 即O（1000log21000）=O(10000) 锦标赛排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089堆排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089若用冒泡排序也较快，最多耗费比较次数为（n-1+n-2+……＋n-10）=10n-55=10000-55=9945（次）4. 答： 01121123435. 答： 要考虑递归时占用了栈空间，但递归次数最多不超过树的高度，所以空间复杂度为O(log2n) 五、 算法设计题1.解：提示：堆的定义是：kia[2*i]|| a[i]>a[2*i+1])return(-1);return(minleap)};else { for( i=1; i<=n/2; i++) if (a[i]lchild) EnQueue(Q,{r.node->lchild, r.layer+1}); if(r.node->rchild) EnQueue(Q,{r.node->rchild, r.layer+1}); } //按层序入队时要随时标注结点所在层号 h=r.layer; //最后一个队列元素所在层就是树的高度 for(maxn=count[0], i=1; h; i++) if(count[i]>maxn) maxn=count[i]; //求出哪一层结点数最多 return (h*maxn)} // Width

一 单项选择题(本大题共 小题 每小题 分 共 分 在每小题的四个备选答案中 选出一个正确答案 并将正确答案的序号填在题干的括号内)

下面程序段的时间复杂度是( )

for(i= ;i

for(j=1;j

A[i][j]=0;

A.O(n) B.O(m+n+1) C.O(m+n) D.O(m*n)

2.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是( )

A.p=p->next; B.p->next=p->next->next;

C.p->next=p; D.p=p->next->next;

3.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=

head,则( )

A.p指向头结点 B.p指向尾结点

C.*p的直接后继是头结点 D.*P的直接后继是尾结点

4.判定“带头结点的链队列为空”的条件是( )

A.Q.front==NULL B.Q.rear==NULL

C.Q.front==Q.rear D.Q.front!=Q.rear

5.设有两个串T和P，求P在T中首次出现的位置的串运算称作( )

A.联接 B.求子串 C.字符定位 D.子串定位

6.广义表A=(a,(b),(),(c,d,e))的长度为( )

A.4 B.5 C.6 D.7

7.一棵含18个结点的二叉树的高度至少为( )

A.3 B.4 C.5 D.6

8.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( )

A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA

9.无向图中一个顶点的度是指图中( )

A.通过该顶点的简单路径数 B.与该顶点相邻接的顶点数

C.通过该顶点的回路数 D.与该顶点连通的顶点数

10.已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为( )

A.a c e f b d

B.a c b d f e

C.a c b d e f

D.a c d b f e

11.在下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是( )

A.快速排序 B.堆排序 C.归并排序 D.基数排序

12.已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。.WingwIT.CoM对这些子序列进行一趟两两归并的结果是( )

A.{25,36,48,72,23,40,79,82,16,35}

B.{25,36,48,72,16,23,40,79,82,35}

C.{25,36,48,72,16,23,35,40,79,82}

D.{16,23,25,35,36,40,48,72,79,82}

13.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( )

A.21 B.23 C.41 D.62

14.索引非顺序文件的特点是( )

A.主文件无序，索引表有序 B.主文件有序，索引表无序

C.主文件有序，索引表有序 D.主文件无序，索引表无序

15.倒排文件的主要优点是( )

A.便于进行插入和删除运算 B.便于进行文件的恢复

C.便于进行多关键字查询 D.节省存储空间

二、填空题 (本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分)

16.抽象数据类型的特点是将____________和____________封装在一起，从而现实信息隐藏。

17.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需____________一个位置。

18.在队列中，允许进行插入操作的一端称为____________，允许进行删除操作的一端称为____________。

19.如图两个栈共享一个向量空间，top1和top分别为指向两个栈顶元素的指针，则“栈满”的判定条件是____________。

20.设S1="good",S2=" ",S3="book"，则S1，S2和S3依次联接后的结果是____________。

21.假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A[9][8][7]的存储地址是____________。

22.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为____________。

23.能够成功完全拓扑排序的图一定是一个____________。

24.如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排序两者之中，选用____________较为适当。

25.假设哈希表的表长为m，哈希函数为H(key)，若用线性探查法解决冲突，则探查地址序列的形式表达为____________。

三、解答题 (本大题共4小题，每小题5分，共20分)

26.假设通信电文使用的字符集为{a,b,c,d,e,f}，名字符在电文中出现的频度分别为：34，5，12，23，8，18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值)，然后分别写出每个字符对应的编码。

27.已知一个图如下所示，其顶点按a、b、c、d、e、f顺序存放在邻接表的顶点表中，请画出该图的邻接表，使得按此邻接表进行深度优先遍历时得到的顶点序列为acbefd，进行广度优先遍历时得到的顶点序列为acbdfe。

28.已知两个4×5的稀疏矩阵的三元组表分别如下：

0 1 4 16 0 1 1 32

1 2 2 18 1 2 2 - 22

2 3 4 - 25 2 2 5 69

3 4 2 28 3 3 4 25

4 4 2 51

请画出这两个稀疏矩阵之和的三元组表。

29.从空树起，依次插入关键字40，8，90，15，62，95，12，23，56，32，构造一棵二叉排序树。

(1)画出该二叉排序树

(2)画出删去该树中元素值为90的结点之后的二叉排序树。

四、算法阅读题 (本大题共4小题，每小题5分，共20分)

30.如图所示，利用同一循环向量空间实现两个队列，其类型Queue2定义如下：

typedef struct {

DataType data[MaxSize];

int front[2],length[2];

} Queue2;

对于 i=0或1,front[i]和length[i]分别为第i个队列的头指针和长度域。请在空缺处填入合适的内容，实现第i个循环队列的入队操作。

int EnQueue(Queue2*Q,int i,DataType x)

{//若第i个队列不满，则元素x入队列，并返回1，否则返回0

if(i<0||i>1)return 0;

if( (1) )

return 0;

Q->data[ (2) ]=x;

Q->length[ (3) ]++;

return 1;

}

(1)

(2)

(3)

31.某二叉树的线索链表存储结构如图(b)所示，其中p为指向根结点的指针，图(a)为结点结构。阅读下列算法，并回答问题：

(1)写出执行函数调用f(p)的输出结果;

(2)简述函数f的功能。

{

while(t)

{

printf(t->data);

if(t->lchild)

t=t->lchild;

else

t=t->rchild;

}

}

(1)

(2)

32.下列函数FindCycle(G,i)的功能是，对一个采用邻接表作存储结构的有向图G，利用深度优先搜索策略寻找一条经过顶点v i 的简单回路。数组cycle_path用于保存搜索过程中形成的回路，cycle_path[k]=j(j≥0)表示在回路中顶点v k 的下一个顶点是v j 。请在空缺处填入合适的内容，使其成为一个完整的算法。

vertex firstedge

已知邻接表的顶点表结点结构为：

adjvex next

边表结点 EdgeNode结构为：

int cycle_path[MaxNum];

int FindCycle(ALGraph*G,int i)

{//若回路存在，则返回1，否则返回0

int j;

for(j=0;j n;j++)cycle_path[j]=-1;

return DFSPath(G,i,i);

}

int DFSPath(ALGraph*G,int j,int i)

{

EdgeNode *p;

int cycled=0;

for(p=G->adjlist[j].firstedge;p&&!cycled;p=p->next)

{

cycle_path[j]=p->adjvex;

if( (1 ) )cycled=1;//已找到回路

else

if(cycle_path[p->adjvex]==-1)cycled= (2) ;

}

return (3)

}

(1)

(2)

(3)

33.阅读下列函数algo,并回答问题。

(1)假设整型数组A[1..8]中的元素依次为(3，8，9，1，7，4，2，6)。执行函数调用algo(A,8)时，外层while的循环体执行多少次?函数的返回值是多少?

(2)简述函数algo(L,n)的功能。

int algo(int L[],intn)

{

int i=0,j,s=1,t=n;

while (i!=(n+1)/2)

{

int x=L[s];

i=s;j=t;

while(i