当前位置：文档之家 › 2011-12数据结构_A_

2011-12数据结构_A_

  • 格式：doc
  • 大小：165.00 KB
  • 文档页数：4

2011--2012学年第 一 学期 经管 学院期末考试卷
《数据结构》（A）
学号: 姓名: 班级:
题号 一 二 三 四 五 总分
得分

得分 评卷教师
一、选择题(每题2分，共30分)。

1.完成在双循环链表结点p之后插入s的操作是
A． p->next=s ; s->prior=p; p->next->prior=s ; s->next=p->next;
B． p->next->prior=s; p->next=s; s->prior=p; s->next=p->next;
C． s->prior=p; s->next=p->next; p->next=s; p->next->prior=s ;
D． s->prior=p; s->next=p->next; p->next->prior=s ; p->next=s;
2.有关二叉树下列说法正确的是
A．二叉树的度为2 B．一棵二叉树的度可以小于2
C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2
3.下面哪一方法可以判断出一个有向图是否有环（回路）
A．深度优先遍历 B. 求最短路径 C. 拓扑排序 D. 求关键路径
4.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等
概率情况下查找成功所需的平均比较次数为______。
A．35/12 B．37/12 C．39/12 D．43/12
5. 平衡树中结点的平衡因子不可能为
A． -1 B． 2 C． +1 D．0
6. 设队列q的最大容量为n，则队满的条件是 。
A.rear-front==n B.rear-front-1==n C.front==rear D.front==(rear+1)%n
7. 若用s[0]~s[n-1]做栈的存储空间，则在删除栈元素s[10]以后，s[10] 。
A.不再是数组元素 B.仍是栈中元素 C.要给s[10]赋一个空值 D.仍然是数组元素
8. 对一个m*m阶的对称矩阵，以行序为主采用压缩存储，其容量为 。
A. m×m B.m×m/2 C.m×(m+1)/2 D.(m+1) ×(m+1)/2
9. 某二叉树的前序遍历序列为ABDGCEFH，中序遍历序列为DGBAECHF，则其后序遍历
序列为 。
A.DBGCEFHA B. GDBECFHA C. BDGAECHF D.GDBEHFCA
10.在任何一棵二叉树中，如果结点a有左孩子b和右孩子c，则在的先序、中序和后序遍历
序列中， 。
A.b一定在a的前面 B.a一定在c的前面 C.b一定在c的前面 D.a一定在b的前面
11.在高度为h的完全二叉树中， 。
A.度为0的结点都在第h层上 B.第i（1≤i

装
订
线
i12. 有n个顶点的无向图的邻接矩阵是用 数组存储的。
A.一维 B.n行n列二维 C.任意行n列 D.n行任意列
13. 具有8个顶点的无向图至少应有 条边才能确保是一个连通图。
A.5 B.6 C.8 D.7
14. 有一个有序表为{2，3，10，12，32，41，45，62，75，78，83，94，99}，当用二分法
查找83时，经过 次比较后查找成功。
A.1 B.2 C.4 D.8
15. 以下排序方法中， 是不稳定的。
A. 希尔排序 B.直接插入排序 C.冒泡排序 D.快速排序

得分 评卷教师
二、判断题（每空1分，共10分）

1. 完全二叉树中的每个结点或者没有孩子或者有2个孩子。（ ）
2. n个结点的二叉树中，总是有n+1个空指针域。（ ）
3. 顺序栈中元素值的大小是有序的。（ ）
4. 对于非空栈来说，栈顶元素和栈底元素都是唯一的。（ ）
5. 循环队列满的条件是：q->rear - q->front==maxsize。（ ）
6. 在循环单链表中，任何一个结点的指针字段值都不可能为空。（ ）
7. 分配给顺序表的内在单元地址一定是连续的。（ ）
8. 在一个小顶堆中，最大值的结点一定是一个叶子结点。（ ）
9. 在n阶带状矩阵中，每一列都有3个非零元素。（ ）
10. 稀疏矩阵的转置矩阵仍然是稀疏矩阵。（ ）

1．一个有n个顶点的无向图最多有________条边，至少应有________条边才能确保是一个
连通图。
2．栈是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表，表中只
允许插入和删除的一端称为栈顶，另一端称之为栈底，这种线性表按照__________________
的原则组织数据。
3．深度为k的完全二叉树至少有_______个结点，至多有________个结点。
4. 根据数据元素之间关系的不同特性，数据结构有集合、线性结构、________________和
图状结构4种基本类型。
5. 根据图的搜索路径方向不同，有两种常用的遍历图的方法，它们是________________和
_________________。
6．衡量一个算法的主要性能指标有 ______________和_______________。

得分 评卷教师
三、填空题（每题1分，共10分）

得分 评卷教师
四、综合题（共50分，请在答题纸上答题）
1.已知稀疏矩阵A的三元组顺序表如图所示（10分）
引入两个数组num[]和position[]，其中num[i]表示矩阵A第i列的非零元个数,position[i]存
放待转置矩阵A中第i列第一个非零元在转置矩阵B中的正确位置。
求num[]和position[]的值，并依据position[]中的数据求A的转置矩阵B的三元组顺序表。
（要有简要过程）
i 0 1 2 3 4 5 6
Num[i]
Position[i]始值
Position[i]终值

2.现有二叉树如图所示，写出该二叉树出先序、中序和后序遍历结果。(6分)

3.现有以下5个结点及其权值，请构造一棵huffman树，并给出huffman编码。（10分，要
有过程，括号中为权值。）
A(1) B(3) C（5） D (6） E（7）

4.用prime算法求图的最小生成树。(10分)
a

bc

de
f

g

10
8
5
17
7

931210

11
164

i j v i j v
0 2 -3
0 5 15
1 0 12
1 4 18
2 0 9
2 3 24
3 5 -7
5 2 14
6 0 32

0 1 2 3 4 5 6 7 8 0
1
2
3
4
5
6
7
8

A
B C
D F G E

H

装
订
线

转置
求解过程：
5. 对关键字（49，38，65，97，76，13，27，4）进行直接选择排序，写出每一步排序过程。
（6分）
6.设关键值集合为{19,7,8,23,16,25,12,26,38,3}，Hash表的长度为13，用线性探测法解决冲突，
给出其Hash表。（要求：给出hush函数，有解题过程，8分）

i k U cost[0] 1 2 3 4 5 6 adj[0] 1 2 3 4 5 6 v-u (u0,v0)
0
1
2
3
4
5
6

合集下载

南方学院2010-2011-1数据结构a

南方学院2010-2011-1数据结构a

南京林业大学南方学院试卷课程 数据结构(A 卷) 2010~2011学年第一学期注意：请将正确答案写在答题纸上，答在试卷上不给分。

一．是非题：（判断下列各题是否正确，正确的在括号内打 “√”，错的打“×”。

每小题2分，共20分）1. 数据的逻辑结构独立于计算机，物理结构依赖于计算机。

2. 算法和程序没有区别，所以在数据结构中两者是通用的。

3. 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

4. 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素。

5. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

6. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

7. 线性表可以看成是广义表的特例，若广义表中的每个元素都是原子，则广义表便成为线性表。

8. 用一维数组存储二叉树时，总是以先序遍历存储结点。

9. 用邻接矩阵存储一个图所需的存储单元数目与图的边数有关。

10. 二叉排序树的查找和折半查找的时间性能相同。

二．选择题（本大题共10小题，每小题2分，共20分）1．被计算机加工的数据元素不是孤立无关的，它们彼此之间一般存在着某种联系。

通常将数据元素之间的这种联系称为______。

A. 规则B. 集合C. 结构D. 运算2．算法的时间复杂度取决于______。

A．问题的规模B．待处理数据的初态C．A与B都对D．算法的易读性3．对于顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。

删除一个元素时所需移动元素次数的期望值为______。

A. n/2B. (n+1)/2C. (n-1)/2D. n4．循环队列用A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，那么当前队列中的元素个数是______。

A．(rear-front+m)%m B．rear-front+1 C．rear-front-1 D．rear-front5．一个非空广义表的表头______。

Eakxei2011年考研计算机大纲

Eakxei2011年考研计算机大纲

生命是永恒不断的创造，因为在它内部蕴含着过剩的精力，它不断流溢，越出时间和空间的界限，它不停地追求，以形形色色的自我表现的形式表现出来。

－－泰戈尔2011 年计算机基础综合考试大纲----数据结构【考查目标】1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。

2.掌握基本的数据处理原理和方法的基础上，能够对算法进行基本的时间复杂度与空间复杂度进行设计与分析。

3.能够选择合适的数据结构和方法进行问题求解，具备采用 C 或 C++或 JA V A 语言设计与实现算法的能力。

一、线性表（一）线性表的定义和基本操作（二）线性表的实现1.顺序存储2.链式存储3.线性表的应用二、栈、队列和数组（一）栈和队列的基本概念（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用（五）特殊矩阵的压缩存储三、树与二叉树（一）树的基本概念（二）二叉树1.二叉树的定义及其主要特征2.二叉树的顺序存储结构和链式存储结构3.二叉树的遍历4.线索二叉树的基本概念和构造（三）树、森林1.书的存储结构2.森林与二叉树的转换3.树和森林的遍历（四）树与二叉树的应用1.二叉排序树2.平衡二叉树3.哈夫曼（Huffman）树和哈夫曼编码四、图（一）图的基本概念（二）图的存储及基本操作1. 邻接矩阵法2. 邻接表法（三）图的遍历1. 深度优先搜索2. 广度优先搜索（四）图的基本应用1. ᳔小（代价）生成树2. ᳔短路径3. 拓扑排序4. 关键路径五、查找（一）查找的基本概念（二）顺序查找法（三）折半查找法（四） B-树及其基本操作、B+树的基本概念（五）散列（Hash）表及其查找（六）查找算法的分析及应用六、内部排序（一）排序的基本概念（二）插入排序1. 直接插入排序2. 折半插入排序（三）起泡排序（bubble sort）（四）简单选择排序（五）希尔排序（shell sort）（六）快速排序（七）堆排序（八）二路归并排序（merge sort）（九）基数排序（十）各种内部排序算法的比较（十一）内部排序算法的应用2011年计算机基础综合考试大纲----计算机组成原理【考查目标】1. 理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式，具有完整的计算机系统的整机概念。

数据结构期末考试试题

数据结构期末考试试题

武汉大学计算机学院2010年－2011学年第一学期“数据结构”考试试题（A）一、单项选择题（每小题2分，共计40分）1. 下列各项中属于逻辑结构的是。

A. 哈希表B. 有序表C. 单链表D. 顺序表2. 以下算法的时间复杂度为。

void fun(int n){ int i=1; while (i<=n) i=i*2; }A. O(n)B. O(n2)C. O(nlog2n)D. O(log2n)3. 在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动个元素。

A. nB. i-1C. n-iD. n-i+14. 判断带头结点的循环单链表L中只有一个结点的条件是。

A. L==NULLB. L->next==LC. L->next->next==LD. L->next==NULL5. 中缀表达式a*(b+c)-d的后缀表达式是。

A. abcd*+-B. abc+*d-C. abc*+d-D. -+*abcd6. 设环形队列中数组的下标是0～N-1，其头尾指针分别为f和r（f指向队列中队头元素的前一个位置，r指向队尾元素的位置），则其元素个数为。

A. r-fB. r-f-1C. (r-f)％N+1D. (r-f+N)％N7. 若用一个大小为6的数组来实现环形队列，队头指针front指向队列中队头元素的前一个位置，队尾指针rear指向队尾元素的位置。

若当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为。

A. 1和5B. 2和4C. 4和2D. 5和18. 稀疏矩阵采用压缩存储后，通常必会失去功能。

A. 顺序存储B. 随机存取C. 输入输出D. 以上都不对9. 一棵有124个叶子结点的完全二叉树，最多有个结点。

A. 247B. 248C. 249D. 25010. n个结点的线索二叉树上含有的线索个数为。

《数据结构》课程期末考试试卷(A卷)DAOAN - 副本

《数据结构》课程期末考试试卷(A卷)DAOAN - 副本

浙江财经学院东方学院2010～2011学年第一学期《数据结构》课程期末考试试卷（A 卷）考核方式：闭卷 考试日期：2010年 月 日 适用专业、班级：东方电子商务专业题 号 一 二 三 四 五 六 总分 得 分 评卷人（共六大题）说明：（1） 请考生将答案写在答题纸上； （2） 考试时间120分钟；一、单选题 （每题1分，共15分）1、对一个算法的评价，不包括如下（ ）方面的内容。

A ．健壮性B ．可读性C ．正确性D ．实用性 2执行下面程序段时，s 语句的执行次数为( D )。

for (int i=l; i<=n;i++) For(int j=1; j<=i; j++)S;A ．n2B ．N2／2C ．n(n+1) D.n(n+1)/2 3..下面算法的时间复杂度为(B) intf (int n){if (n==0 || n==l) return 1. Else return n*f(n-l);A ．O(1)B ．O(n)C ．O(n2)D O(n!)4、在一个长度为n 的顺序存储的线性表中，删除第i 个元素(1≤i ≤n)时，需要从前向后依次前移( A )个元素。

A. n-iB.n-i+1C.n-i-lD.i5若一个结点的引用为p ，在p 结点后面插入一个值为x 的新结点的操作为( D )。

A. p=new Node(x,p) B.p=new Node(x,p. next)密 封 线专业、班级： 学号： 姓名：C. p.next=new Node(x,p)D.p.next=new Node(x,p. next)6假定利用数组a顺序存储一个栈，用top表示栈顶指针，top-= -1表示栈空，并已知栈不为空，当退栈并返回栈顶元素时所执行的操作为( B )。

A.return a[- -top];B.return a[top--];C. rcturn a[++top];D.return a[top++];7若让元素1．2.3依次进栈．则出栈次序不可能出现( C )的情况。