2008-09(1)数据结构期末试卷(A)

汕 头 职 业 技 术 学 院

2008-2009学年第一学期期末试卷（A）

课程名称 数据结构 学分_____ 拟题人 何汉阳 审题人___________ 系(校区) 计算机系 班级_____________ __ 学号_____ 姓名_ _________

题 号 得 分 一 二 三 四 五 六 七 八 总 分 评卷人

一、选择题（每小题2分，共40分）

1．数据的__________包括集合、线性结构、树型结构和图状结构四种基本类型。 A)算法描述 B)基本运算 C)逻辑结构 D)存储结构

2．数据的存储结构包括顺序、___________、索引和散列四种基本类型。 A)向量 B)数组 C)集合 D)链接

3．下面____________的时间复杂性最好，即执行时间最短。

3

A)O(n) B)O(nlog2n) C)O(log2n) D)O(n)

4．在一个长度为n的顺序表中，向第i个元素(1≤i≤n+1)位置插入一个新元素时，需要从后向前依次后移_________个元素。

A) n-i B) i C) n-i-1 D) n-i+l

5．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的，插入一个元素时平均移动表中的_______个元素。

A) n/2 B) (n-1)／2 C) (n+1)／2 D) n

6．单链表要求内存中可用存储单元的地址 。

A)必须是连续的 B)一定是不连续的

C)部分地址必须是连续的 D)可以是连续的，也可以是不连续的

7．在一个单链表中，若要删除p指针所指向结点的后继结点，则执行________。 A)p->next=p B)p=p->next->next

C)p->next=p->next->next D)p=p->next；p->next=p->next->next

8．若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用______存储方式最节省时间。

A)单链表 B)双链表 C)单循环链表 D)带头结点的双循环链表

9．采用链接方式存储线性表的优点是_________。

A)便于随机存取 B)花费的存储空间较顺序存储少

C)便于插入和删除操作 D)数据元素的物理顺序和逻辑顺序相同

10．在下面栈的基本运算中，不是加工型运算的是_______。 A)初始化 B)进栈 C)退栈 D)判栈空

- 1 -

11．在顺序栈中进行退栈操作时，___________。

A)谁先谁后都可以 B)先移动栈顶指针，后取出元素 C)不分先后，同时进行 D)先取出元素，后移动栈顶指针

12．假设一个栈的输入序列为A，B，C，D，E，则下列序列中不可能是栈的输出序列的是_______。 A)B，C，D，A，E B)E，D，A，C，B C)B，C，A，D，E D)A，E，D，C，B

13．在由n个单元组成的顺序存储的循环队列sq中，假定f和r分别为队头指针和队尾指针，则判断队满的条件是_______。

A)f == (r十1)％n B) (r-1)％n == f C)f == r D) (f+1)％n == r

14．树最适合于表示__________。

A)有序数据元素 B)无序数据元素

C)元素之间无联系的数据 D)元素之间具有分支层次关系的数据

15．在一棵深度为k的完全二叉树中，所含结点个数不小于_________。

kkkk-1

A)2 B)2+1 C)2-1 D)2

16．在下列存储形式中，_______不是树的存储形式。 A)双亲表示法 B)顺序存储表示 C)孩子兄弟表示法 D)孩子链表表示法

17．对于长度为8的顺序存储结构的有序表，若采用二分查找法查找，在等概率的情况下的平均查找长度为__________的值除以8。

A)17 B)19 C)21 D)20

18．若对n个元素进行直接插入排序，则进行第i趟排序过程前，有序表中的元素个数为_______。 A)1 B)i-1 C)i D)i+l 19．在对n个元素进行冒泡排序的过程中，第一趟排序至多需要进行_______。 对相邻元素之间的交换。 A) n／2 B) n-1 C) n D) n+l

20．以下四种排序方法中，需要附加的内存空间最大的是________。 A)插入排序 B)选择排序 C)快度排序 D)归并排序

二、判断题（每小题1分，共15分）

1、数据的物理结构是指数据在计算机内的实际存储形式。（ ） 2、分配给单链表的内存地址必须是连续的。（ ）

3、在有n个元素的顺序表中，删除任意一个元素所需移动结点的平局次数为n-1。（ ） 4、对于单循环链表，从表中任一结点都能扫描表中的全部结点。（ ） 5、栈是一种对进栈、出栈操作总次数做了限制的线性表。（ ） 6、在n个元素进栈后，它们的出栈顺序和进栈顺序一定正好相反。（ ）

- 2 -

7、疏矩阵的特点是矩阵中的元素较少。（ ） 8、哈夫曼树中不存在度为1的结点。（ ）

9、存在这样的二叉树，对它采用任何次序的遍列，结果相同。（ ）

10、只要知道完全二叉树中结点的先序序列，就可以唯一确定它的逻辑结构。（ ） 11、如果表示有向图的邻接矩阵是对称矩阵，则该有向图一定是完全有向图。（ ） 12、有向图的遍历不可采用广度优先搜索方法。（ ）

13、顺序表和单链表表示的有序表均可使用二分查找法来提高查找速度。（ ）

14、只有在记录的关键字的初始状态为逆序排列的情况下，直接选择排序过程中元素的移动次数才会达到最大值。（ ）

15、内排序中的快速排序方法，在任何情况下均可得到最快的排序效果。（ ）

三、列表说明用Prim算法求解下图最小生成树的生成过程。（15分）

- 3 -

四、在一个递增有序的无头结点的单链表中，有数值相同的元素存在。设计算法去掉数值相同的元素，使表中不再有重复的元素。（10分）

五、写出一个m×n阶t个非零元素、采用三元组法存储的稀疏矩阵改进的transpot转置的算法子程序，要求算法总的时间复杂度为O(n+t)。（10分）。

- 4 -

六、写出顺序表上将监视哨设在高端的顺序查找算法子程序，并要写出在main()主函数中调用的过程语句。查找表的结构定义同课本一致，查找表的元素值和长度通过键盘输入。（10分）。

- 5 -

2008-2009学年第一学期期末试卷（A）答案

课程名称 数据结构 拟题人 何汉阳

一、选择题（每小题2分，共40分）

1～5、CDCDA 6～10、DCDCD 11～15、DBADD 16～20、DBCBD

二、判断题（每小题1分，共15分）

1～5、√××√× 6～10、××√√√ 11～15、×××√×

三、解：（15分） 从顶点0出发 U={0}, V-U={1, 2, 3, 4, 5, 6} Adjvex / 0 0 0 0 0 0 k=5 Lowcost 0 28 ∞ ∞ ∞ 10 ∞ (0, 5) 0??028???10U={0, 5}, V-U={1, 2, 3, 4, 6} 128016??Adjvex / 0 0 0 5 0 0 k=4 2???3??16012??Lowcost 0 28 ∞ ∞ 25 0 ∞ (5, 4) ???12022?U={0, 5, 4}, V-U={1, 2, 3, 6} 4????22025Adjvex / 0 0 4 5 0 4 k=3 5??10???250Lowcost 0 28 ∞ 22 0 0 24 (4, 3) 6???14?1824?U={0, 5, 4, 3}, V-U={1, 2, 6} Adjvex / 0 3 4 5 0 3 k=2 Lowcost 0 28 12 0 0 0 18 (3, 2) U={0, 5, 4, 3, 2}, V-U={1, 6} Adjvex / 2 3 4 5 0 3 k=1 Lowcost 0 16 0 0 0 0 18 (2, 1) U={0, 5, 4, 3, 2, 1}, V-U={ 6} Adjvex / 2 3 4 5 0 1 k=6 Lowcost 0 0 0 0 0 0 14 (1, 6) U={0, 5, 4, 3, 2, 1, 6}, V-U={ } 四、解：（10分）

void DelSameNode(LinkList *L) //L是递增有序的单链表 { LinkList *p, *pre, *q;

pre = L; //pre是p所指向的前驱结点的指针

p = pre->next; //p是工作指针。设链表中至少有一个结点 while(p != NULL)

if(p->data == pre->data) //处理相同元素值的结点 { q=p; p=p->next; free(q); } //释放相同元素值的结点 else

{ pre=p; p=p->next; } //处理前驱，后继元素值不同 pre->next=p； //置链表尾 }

??????18??24????0??- 6 -

14五、解：（10分）

SPMatrix *TransM2(SPMatrix *A) { SPMatrix *B; int i,j,k;

int num[n+1],cpot[n+1];

B=malloc(sizeof(SPMatrix)); /*申请存储空间*/

B->mu=A->nu; B->nu=A->mu; B->tu=A->tu; /*行、列、元素个数*/ if(B->tu>0) /*有非零元素则转换*/

{ for (i=1;i<=A->nu;i++) num[i]=0;

for (i=1;i<=A->tu;i++) /*求矩阵A中每一列非零元素的个数*/ { j= A->data[i].j; num[j]++; }

cpot[1]=1; /*求矩阵A中每一列第一个非零元素在B.data中的位置*/ for (i=2;i<=A->nu;i++)

cpot[i]= cpot[i-1]+num[i-1];

for (i=1; i<= (A->tu); i++) /*扫描三元组表*/ { j = A->data[i].j; /*当前三元组的列号*/

k = cpot[j]; /*当前三元组在B.data中的位置*/ B->data[k].i = A->data[i].j; B->data[k].j = A->data[i].i; B->data[k].v = A->data[i].v; cpot[j]++; } /*for i */ } /*if (B->tu>0)*/

return B; /*返回的是转置矩阵的指针*/ }

六、解：（10分）

#include #define MAXSIZE 100 void main() typedef struct { int k,i; { int key; SSTABLE st; }SSELEMENT; printf(\typedef struct

scanf(\{ SSELEMENT r[MAXSIZE]; for(i=0; i

printf(\int seq_search(int k, SSTABLE st) scanf(\{ int j=0; i=seq_search(k, st); st.r[st.len].key=k; printf(\ while(st.r[j].key!=k) j++; } if(j

return j+1; else return 0; }

- 7 -

本文来源：https://www.bwwdw.com/article/tneg.html