号： 滁州学院2011/2012 学年度第二学期期末考试试卷
计算机网络工程专业(本科)2011级《数据结构》A卷（时间120分钟） 题号 一 二 三 四 总分 C. x=q[front]；front=front-1； D. front=(front-1)%m；x=q[front]；
8．以下叙述中正确的是( )。 A.串是一种特殊的线性表 B.串的长度必须大于零 C.串中无素只能是字母 D.空串就是空白串
9. 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为( )。 学 题 ： 名答 姓 要 不 内 线 ： 订 班级 装/级年 ：业专分值 20 30 30 20 100 A. SA+141 B. SA+180 C. SA+222 D. SA+225
得分 10. 树最适合用来表示( )。
A.有序数据元素 B.无序数据元素
一、选择题（每小题1分，共20分）
C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据
11. 深度为5（根的层次为1）的二叉树至少有( )结点。 1．下面关于线性表的叙述错误的是( )。
A. 16 B. 15 C. 5 D. 31 A. 线性表采用顺序存储必须占用一片连续的存储空间 12. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少B. 线性表采用链式存储不必占用一片连续的存储空间 为( )。
A. 2h B. 2h-1 C. 2h+1 D. h+1 C. 线性表采用链式存储便于插入和删除操作的实现
13. 按二叉树的定义，具有3个结点的二叉树有( ) 种。 D. 线性表采用顺序存储便于插入和删除操作的实现
A. 6 B. 5 C. 4 D. 3
2．已知某数据结构的二元组形式表示为：A=(D，R)，D={01，02，03，04，05，06，07，08，
14.一棵深度为5的完全二叉树的第5层有5个结点，则叶子结点有( )个。 09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，A. 10 B. 5 C. 16 D. 8
<03，08>，<03，09>}。则此数据结构属于( )结构。 15．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中A. 线性结构 B. 顺序结构 C. 图型结构 D. 树型结构 的结点数为( )。 3．下面程序的时间复杂为( )。
A.k1 B.k2 C.k1-k2 D.k1+k2
for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} 16．判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用( )。 A. O(n) B. O(n2) C. O(n3) D. O(n4)
A. 求关键路径的方法 B. 求最短路径的Dijkstra方法 4．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列C. 广度优先遍历算法 D. 深度优先遍历算法 为( )。
17. 已知有向图G的二元组形式表示为G=（D，R），其中D={V1，V2，V3，V4，V5，V6}，A. q=p->next；p->data=q->data；p->next=q->next；free(q)； R={
C. v1，v4，v2，v3，v6，v5 D. v1，v4，v6，v2，v5，v3 5．栈和队列的共同特点是( )。
18.对线性表进行二分查找时，要求线性表必须( )。 A.只允许在端点处插入和删除元素 B. 都是先进后出指针 A. 以顺序方式存储 C. 都是先进先出 D. 没有共同点
B. 以链接方式存储
6. 设用一维数组s[m]表示栈的存储空间，用top指向当前栈顶元素（其初始值为-1），则进C. 以顺序方式存储，且结点按关键字有序排序 行入栈时的操作序列是( )。 D. 以链接方式存储，且结点按关键字有序排序
A. s[top] =x； B. top=top+1；s[top]=x； 19．对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为( )。 C. top==top-1；s[top]=x； D. s[top]=x；top==top+1；
A. 从第0个元素往后查找该数据元素 7.设用一维数组q[m]作为顺序循环队列的存储空间，front指向队头元素的前一个位置，rearB. 从第1个元素往后查找该数据元素 指向队尾元素的当前位置，则出队列的操作序列为( )。 C. 从第n个元素往开始前查找该数据元素 A. x=q[front]；front=front+1； B. front=(front+1)%m；x=q[front]；
D. 与查找顺序无关
《数据结构》期末试卷本卷共4 页第1页
20.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。 A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序
功的结点数有_______个，比较五次查找成功的结点数有______个，平均查找长度为_______。 14. 设哈希表长m=14，哈希函数H(key)=key。表中已有4个结点：
addr (15)=4; addr (38)=5; addr (61)=6; addr (84)=7
如用二次探测再散列处理冲突，关键字为49的结点的地址是____________。 15. 平衡二叉排序树上任一结点的平衡因子只可能是________、________或-1。
16. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较____________。
17. 在插入和选择排序中，若初始数据基本正序，则选用____________；若初始数据基本反序，则选用____________。
二、填空题（每空1分，共30分）
1. 数据结构的逻辑结构包括_____________、树型结构和图型结构三种类型，其中树型结构和图型结构合称为_____________；数据结构的存储结构主要包括____________和____________两种类型。
2. 设长度为n的顺序线性表在任何位置上插入或删除操作都是等概率的，则插入一个元素时平均需要移动____________个元素，删除一个元素时平均需要移动____________个元素。 3. 对于一个具有m个存储单元的顺序循环队列，设front为队头指针，rear为队尾指针，则该队列中队列元素的个数计算公式为____________。
4. 一个队列的数据入列序列是A，B，C，D，则队列的出队时输出序列是_____________________。
5. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为____________。
6. 设二维数组A有m行n列，每个数组元素占L个字节的存储单元，按行的顺序存放在m*n个连续的存储单元中。已知A[0][0]的地址为1000，则A[i][j]的地址为____________。 7. 广义表GetTail[GetHead[((a,b),(c,d))]]操作的结果为____________。
8. 假设一棵二叉树中，双分支结点数为15个，单分支结点数为30个，则终端结点数为________。 9. 由如图1所示的二叉树，回答以下问题：
⑴ 其中序遍历序列为____________________。 ⑵ 其前序遍历序列为____________________。 ⑶ 其后序遍历序列为____________________。
dj b eh i 图1 一棵二叉树
三、简答题（每小题6分，共30分）
1. 对于一个栈，给出输入项1，2，3。如果输入项序列由1，2，3组成，试给出全部可能的输出序列。
2. 假设用于通信的电文仅由8个字母 {a, b, c, d, e, f, g, h} 构成，它们在电文中出现的概率分别为{ 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10}，试画出相应的赫夫曼树，并设计赫夫曼编码。要求，左子树的权值小于右子树，编码时，左子树取0 ，右子树取１。
c f
a 10. 一个有n个顶点的无向图最多有____________条边。在一个具有n个顶点的无向图中，要连通全部顶点至少需要____________条边。
11．在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i ]等于____________。
12. 设无向图G中有e条边且所有顶点的度数之和为m，则m与e之间的关系为____________。 13. 假设在有序表R[0：19]上进行二分查找，则比较一次查找成功的结点数有1个，比较两次查找成功的结点数有_______个，比较三次查找成功的结点数有_______个，比较四次查找成
《数据结构》期末试卷本卷共4 页第2页
3. 设一棵树的二元组形式表示为{(a，b)，(a，c)，(a，d)，(b，e)，(c，f)，(c，g)}，要求用孩
子兄弟表示法表示出该树的存储结构并将该树转化为对应的二叉树。
4. 已知无向网G如右图2所示，给出应用Kruskal算法构造最小生成树的过程。
6 1 5 4 1 7 6 2 5
3 5 3 4
2
5 6 6 图 2 无 向网
5．已知AOE网有9个结点：V1，V2，V3，V4，V5，V6，V7，V8，V9，其邻接矩阵如下：(1)请画出该AOE图。(2)计算完成整个计划需要的时间。(3)求出该AOE网的关键路径。 ∝ 6 4 5 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 1 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 1 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 2 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 9 7 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 4 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 2 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 4 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝
4 页第3页
《数据结构》期末试卷本卷共四、算法设计题（每小题10分，共20分）
1. 线性表的链式存储结构的类型定义如下。 typedef int DataType; typedef struct node{
DataType data; /*每个元素数据信息*/
struct node *next; /*存放后继元素的地址*/ } LNode, *LinkList; 请将下面代码补充完整。
//查找单链表H的第i个位置所在的结点; LinkList Locate_LinkList( LinkList H, int i) { }
2. 二叉树的链式存储结构定义如下： typedef struct BiTNode {
ElemType data;
struct BiTNode *lchild, *rchild; }BiTNode,*BiTree;
请编写一算法实现按先序序列建立二叉树的二叉链表的过程。4 页第4页
《数据结构》期末试卷本卷共
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构 A卷在线全文阅读。
相关推荐：