数据结构期末考试试题和标准答案及评分标准(2)

二、填空题（本大题共10个空，每空2分，共20分）

1．数据结构包含三个方面的内容，即数据的逻辑结构 、数据的 结构和对数据所施加的操作。

2．已知指针q值为NULL、指针p指向单链表L中的某结点，则删除其后继结点（要求由指针q指向）的语句是 ， ，free(q)。 3．设广义表L=（a,( )） ,则Head(L)= 。

4．当且仅当两个串的 相等并且各个对应位置上的字符都相等时，称这两个串相等。 5.二叉树的第4层结点数最多为 个。 6．除了利用求关键路径的方法，还可以利用 方法判断出一个有向图是否有环（回路）。

7．图的遍历主要有 和 两种方法。 8. 具有4个顶点的无向完全图有 条边。

三、判断题（本大题共10小题，每题1分，共10分）

（请在每小题后面的括号里写出答案，如果正确，请写“√”，如果错误，请写“×”） 1.对于一个线性表，采用顺序存储方式进行插入和删除结点时效率太低，采用链式存储方式更好。（ ） 2.所谓静态链表就是一直不发生变化的链表。（ ） 3.在顺序表中，最后一个元素有一个后继。（ ） 4.线性表就是链式存储的表。（ ）

5.串是一种特殊的线性表，其特殊性体现在数据元素可以是多个字符。（ ） 6.对稀疏矩阵进行压缩存储的目的是便于输入和输出。（ ） 7.任意一棵二叉树中的度可以小于2。（ ）

8.树形结构最适合用来表示元素之间具有分支层次关系的数据。（ ）

9.当采用分块查找时，数据的组织方式为：数据分成若干块，每块内数据必须有序。（ ） 10.顺序查找法适合于存储结构为顺序存储或链式存储的线性表。（ ）

四、应用题（本小题共5小题，每小题6分，共30分）

1. 下面是对二叉树进行操作的算法，其功能为 （6分） Void unknown(Btree BT) { Btree p=BT,temp; If(p!=NULL) { temp=p->lchild; p->lchild=p->rchild; p->rchid=temp; unknown(p->lchild);

unknown(p->rchild); }

2. 请写出如图4.1所示二叉树的先序遍历序列、中序遍历序列和后序遍历序列。（6分）

A

B

ECFGD 6

图4.1 二叉树

3．已知如图4.2所示的有向图，请给出：（共6分）

① 每个顶点的入度和出度；（2分）

图4.2 有向图

② 邻接矩阵；（4分）

4.要求用普里姆算法画出如图4.3所示无向网的最小生成树，假设从a顶点出发构造最小生成树，写出各条边加入生成树的次序（用权值表示）。（6分）

图4.3 无向网

5.下列算法的运行结果是 （栈的元素类型为char）(6分) void main()

{ stack S;

char x=’a’,y=’b’; initstack(S);

push(S,x); push(S,y); printf(“%c”,x); printf(“%c”,y); pop(S,x); pop(S,y); printf(“%c”,x); printf(“%c”,y);}

7

五、算法设计题（本大题共1小题，每题10分，共10分）

1. 已知查找表的数据元素类型如下： Typedef struct Rectype {int num; char name[8]; }Rectype;

假设查找表中有n个记录，并且是采用顺序存储 Typedef Rectype Sqlist[100]; 要求：（1）写出对给定值K进行从前端开始顺序查找的算法和main函数。

（2）顺序查找算法的函数头部为“int search(Sqlist R,int n,int K) “ （3）在main函数中建立该查找表、调用顺序查找算法，并输出查找结果。

8

《 数据结构 》（A卷）试题标准答案及评分标准

一、单项选择题（ 本大题共15小题，每小题2分，共计30分）

1.B 2.B 3.C 4.A 5.A 6.B 7.C 8.B 9.B 10.C 11.A 12.B 13.D 14.D 15.C

二、填空题（本大题共10个空，每空2分，共计20分） 1.对象 2.q->next=s,s->net=p 3.数据 4.（b,c,d） k

5.2-1 6.v1,v3,v4,v6,v2,v5,v7 7.n-1 8.邻接矩阵，邻接表（不分先后） 三、判断题（本大题共10小题，每小题1分，共计10分） 1.× 2.× 3.√ 4.√ 5.× 6.√ 7. × 8. × 9.√ 10.× 四、应用题（本大题共5小题，每小题6分，共30分）

1．利用栈将队列中的元素逆置（6分） 2.（6分） ABEFGCD

3. （6分）其中：哈夫曼树（2.5分）

哈夫曼编码（3.5分）a:10 b:110 c:111 d:0111 e:00 f:0110 g:011 4.（6分）其中深度优先搜索序列为v1,v2,v3,v6,v5,v4 (3分)

广度优先搜索序列为v1,v2,v5,v4,v3,v6 (3分) 5.（6分）

五、算法设计题（10分）

int binsearch(Sqlist R,int n,int K) （5分） [int low=0,high=n-1,mid;

while(low<=high) {mid=(low+high)/2;

if(R[mid].key==K) return mid;

else if(R[mid].key>K) low=mid+1; else high=mid-1; }

return -1; } main() (5分)

{ Sqlist R ; int n,k,i;

scanf(“%d”,&n);

for(i=0;i

{scanf(“%d\\n”,&R[i].num); gets(R[i].name); } scanf(“%d”,&k); i=binsearch(R,n,k);

if(i==-1) printf(“nof found!”); else printf(“found!”); }

荆楚理工学院成人高等教育期末考试

9

《 数据结构 》（B卷）试题标准答案及评分标准

一、单项选择题（本大题共15小题，每小题2分，共计30分）

1.A 2.B 3.A 4.A 5.C 6.C 7.A 8.B 9.A 10.B 11.A 12.A 13.C 14.C 15.C

二、填空题（本大题共10个空，每空2分，共计20分） 1.存储（物理） 2.q=p->next,p->next=q->next 3.a 4.长度 5.8 6.拓扑排序 7.深度优先搜索遍历，广度优先搜索遍历（不分先后） 8.6 三、判断题（本大题共10小题，每小题1分，共计10分）

1.√ 2.√ 3.× 4.× 5.× 6.× 7. √ 8.√ 9. × 10.√ 四、应用题（本大题共5小题，每小题6分，共30分） 1．（6分）将二叉树中的左右子树交换 2.（6分）其中先序遍历序列为ABEFCDG（2分）

中序遍历序列为EFBCGDA（2分） 后序遍历序列为FEGDCBA（2分） 3.（①2分 ②4分,共6分）

4. （6分） (最小生成树4分，次序2分，共6分) 次序：1,4,3,9,23

5.abba （6分）

五、算法设计题（10分）

int search(Sqlist R,int n,int K) (5分)

[int i;

for(i=0;i

main() （5分）

{ Sqlist R ; int n,k,i;

scanf(“%d”,&n);

for(i=0;i

if(i>=n) printf(“nof found!”); else printf(“found!”); }

10