数据结构考试(数据结构（C#语言版）笔试试题与答案)

《数据结构》期末考试试卷（ A ）

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

1．计算机识别、存储和加工处理的对象被统称为( A )

A.数据 B.数据元素

C.数据结构 D.数据类型

2．栈和队列都是（ A ）

A．限制存取位置的线性结构 B．顺序存储的线性结构

C．链式存储的线性结构 D．限制存取位置的非线性结构

3．链栈与顺序栈相比，比较明显的优点是( D )

A.插入操作更加方便 B.删除操作更加方便

C.不会出现下溢的情况 D.不会出现上溢的情况

4．采用两类不同存储结构的字符串可分别简称为( B )

A.主串和子串 B.顺序串和链串

C.目标串和模式串 D.变量串和常量串

5． 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是：B

A. 110 B .108

C. 100 D. 120

6．串是一种特殊的线性表，其特殊性体现在：B

A.可以顺序存储 B .数据元素是一个字符

C. 可以链接存储 D. 数据元素可以是多个字符

7．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为： C

A. 2h B .2h-1

C. 2h+1 D. h+1

软件开发网 www.mscto.com

8．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把 由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确？ A

A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同

B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同

C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同

D. 以上都不对

9．一个有n个顶点的无向图最多有多少边？C

A. n B .n(n-1)

C. n(n-1)/2 D. 2n

10．在一个图中，所有顶点的度数之和等于所有边数的多少倍?C

A. 1/2 B .1

C. 2 D. 4

11．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（ A ）

A．左子树的叶子结点 B．左子树的分支结点

C．右子树的叶子结点 D．右子树的分支结点

软件开发网 www.mscto.com

12．对于哈希函数H(key)=key%13,被称为同义词的关键字是( D )

A.35和41 B.23和39

C.15和44 D.25和51

二、已知某棵二叉树的前序遍历结果为A,B,D,E,G,C,F,H,I,J，其中中序遍历的结果为D,B,G,E,A,H,F,I,J,C。请画出二叉的具体结构。（注意要写出具体步骤）（10分）

原理见课本128页

三、有图如下，请写出从顶点c0出发的深度优先及宽度优先遍历的结果。(10分)

深度优先；C0-C1-C3-C4-C5-C2

宽度优先：C0-C1-C2-C3-C4-C5

四、有图如下，按Kruskal算法求出其最小生成树。要求写出完整的步骤。（10分）

原理见课本250页

五、给定线性表（12，23，45，66，76，88，93，103，166），试写出在其上进行二分查找关键字值12，93，166的过程。并写出二分查找的算法。（20分）

0 1 2 3 4 5 6 7 8

12 23 45 66 76 88 93 103 166

过程：

mid=(0+8)/2=4

high=3,low=0 mid=1

high=0,low=0 mid=0（找到12）

high=8,low=5,mid=6（找到93）

high=8,low=7,mid=7

high=8 low=8 mid=8

算法：见课本84页上

六、知单链表的结点结构为

Data next

下列算法对带头结点的单链表L进行简单选择排序，使得L中的元素按值从小到大排列。

请在空缺处填入合适的内容，使其成为完整的算法。 (可用文字说明该算法的基本思想及执行的过程，10分)

void SelectSort(LinkedList L)

{

LinkedList p,q,min;

DataType rcd;

p= (1) ;

while(p!=NULL) {

min=p;

q=p->next;

while(q!=NULL){

if( (2) )min=q;

q=q->next;

}

if( (3) ){

rcd=p->data;

p->data=min->data;

min->data=rcd;

}

(4) ;

}

}

本题不会。嘿嘿。。。。

七、一个完整的算法应该具有哪几个基本性质？分别简要说明每一性质的含意。(5分)

输入：

四个基本性质：1.输入：有零个或多个有外部提供的量作为算法的输入

2：输出：算法产生至少一个量作为输出

3.：确定性：组成算法的每条指令是清晰的，无歧异的。

4.：有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的

八、何谓队列的"假溢"现象？如何解决？（5分）

队列的假溢现象是指数组实现的顺序队列中，队尾指针已到达数组的下表上界产生上溢而队头指针之前还有若干 空间闲置的现象。解决的办法之一是利用循环队列技术使数组空间的首尾相连。

九、说明并比较文件的各种物理结构。（6分）

408考试分值分布如下：

数据结构45分

计算机组成原理45分

操作系统35分

计算机网络25分

选择题80分包括：数据结构（ 1~11题 ）22分；计算机组成原理（ 12~22题 ）22分；操作系统 （23~32题） 20分；计算机网络 （33~40题） 16分

七道综合应用题共70分

计算机考研408是全国统考的科目，对计算机类考研考生来说，选择自命题科目的高校及科研院所数量越来越少，不少高校选择使用408计算机学科专业基础综合来代替以往的考试科目。