06数据结构（50分）
一、单选题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填写在题干后面的括号内。每小题1分，共10分）
1.数据的基本单位是（）
A.数据项
B.数据类型
C.数据对象
D.数据元素
2.若频繁的对线性表进行插入和删除操作，则该线性表应该采用_______存储结构。（）
A.顺序
B.链式
C.散列
D.任意
3.若进栈序列为3，5，7，9，进栈过程中可以出栈，则不可能的出栈次序是（）
A.7，5，3，9
B.9，7，5，3
C.7，5，9，3
D.9，5，7，3
4.下面的说法中，正确的是（）
A.字符串的长度指串中包含的字母的个数
B.字符串的长度指串中包含的不同字符的个数
C.一个字符串不能说是其自身的一个子串
D.若T包含在S中，则T一定是S的一个子串
5.广义表（（a，b），（c，d））的表尾是（）
A.d
B.c，d
C.（c，d）
D.（（c，d））
6.n个顶点的连通图，其生成树有_______条边。（）
A.n-1
B.n
C.n+1
D.不确定
7.若一棵二叉树有8个度为2的结点，则该二叉树的叶节点个数为（）
A.7
B.8
C.9
D.不确定
8.在有n个节点的二叉链表中有_______个空链域。（）
A.n+1
B.n
C.n-1
D.不确定
9.在等概率的情况下，采用顺序插查找法查找长度为n的线性表，平均查找长度为（）
A.n
B.n/2
C.(n+1)/2
D.(n-1)/2
10.下列排序方法中，排序的比较次数与序列的初始排列状态无关的是（）
A.选择排序
B.插入排序
C.冒泡排序
D.快速排序
二、填空题（本大题共10小题，每小题1分，共10分）
1.假定一个顺序队列的队首和队尾分别为f和r，则判断队空的条件为__________________。
2.在顺序存储的线性表中插入或删除一个元素平均约移动表中__________________的元素。
3.设有一个二维数组A[5][4]，按行序优先存储，A[0][0]的存储地址是10，每个数组元素占2个字节，则A[3][2]的存储地址是______________。
4.深度为k的二叉树至多有______________个结点。（k≥1）
5.在有n个结点，e条边的有向图的邻接表中有_________________个表结点。
6.对一棵二叉树进行___________遍历时，得到的结点序列是一个关键字的有序序列。
7.在一个图中，所有顶点的度数之和是边数的____________倍。
8.若有序表（15，21，33，46，58，80，87）中折半查找元素33时，与关键字比较________次查找成功。
9.设哈希表长m=14，哈希函数H(key)=key MOD 11。表中已有4个元素：
如果用二次探测再散列处理冲突，关键字为49的记录的存储位置是______________。
10.具有n个顶点的无向完全图，有____________________条边。
三、判断题（本大题共5小题，每小题1分，共5分）
1.算法在执行时，对同样的输入可以得到不同的结果。（）
2.线性表的链式存储结构的内存单元地址一定不连续。（）
3.队列允许插入的一段成为队尾，允许删除的一端称为队头。（）
4.拓扑排序是内部排序。（）
5.树转换成二叉树，其根结点的右子树一定为空。（）
四、综合应用题（本大题共3小题，每小题5分，共15分）
1.画出具有三个结点的二叉树的所有形态（不考虑数据信息的组合情况）。（5分）
2.写出下图的邻接矩阵，并写出其从V1出发的深度优先搜索遍历序列（5分）
3.将下图所示的树转换成二叉树，并写出该二叉树的先序遍历序列。（5分）
五、算法设计（本大题共1小题，共10分）
1.已知线性表采用链式存储结构，结点类型定义如下，试编写一个算法，在带头结点的单链表L中，删除所有值为x的结点。
typedef struct LNode
{ElemType data;
struct LNode *next;
}LNode,*Linklist;
07数据结构（50分）
一、单项选择题（10分，每题1分）
1.按二叉树的定义，具有3个结点的二叉树有________种。（）
A.3
B.4
C.5
D.6
2.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）
A.i
B.n=i
C.n-i+q
D.不确定
3.下面结论________是正切的。（）
A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B. 树的后根遍历序列与其对应的二叉树的先序遍历序列相同
C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D.以上都不对
4.评价一个算法时间性能的主要标准是（）
A.算法易于调试
B.算法易于理解
C.算法的稳定性和正确性
D.算法的时间复杂度
5.线性表的顺序存储结构是一种__________的存储结构。（）
A.随机存取
B.顺序存取
C.索引存取
D.散列存取
6.在顺序表中，只要知道__________，就可在相同时间内求出任一结点的存储地址。（）
A.基地址
B.结点大小
C.向量大小
D.基地址和结点大小
7.在中序线索二叉树中，若某结点有右孩子，则该结点的直接后继是（）
A.左子树的最右下结点
B.右子树的最右下结点
C.左子树的最左下结点
D.右子树耳朵最左下结点
8.一个栈的入栈序列是abcde，则栈的不可能输出序列是（）
A.edcba
B.decba
C.dceab
D.abcde
9.广义表是线性表的推广，它们之间的区别在于（）
A.能否使用子表
B.能否使用原子项
C.表的长度
D.是否能为空
10.若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点的个数是（）
A.9
B.11
C.12
D.不确定
二、填空题（每空1分，共10分）
1.顺序表中逻辑上相邻的元素的物理位置_____________________。
2.在分块查找方法中，首先查找索引表，然后再用顺序查找方法查找相应的______________。
3.分配排序的两个基本过程是_______________________。
4.在拓扑排序中，拓扑序列的第一个顶点必定是_________________为0的顶点。
5.有n个结点的二叉链表中。其中空的指针域为__________________________。
6.有向图的邻接表表示适于求顶点的____________________。
7.有向图的邻接矩阵表示中，第i____________________上非零元素的个数为顶点vi的入度。
8.在树的_________________表示法中，求指定结点的双亲或祖先十分方便，但是求指定结点的孩子或其他后代可能要遍历整个数组。
9.由五个分别带权值为9,2,3,5,14的叶子结点构成一棵哈夫曼树，该树的带权路径长度为____________________。
10.具有n个顶点的有向图最多有________________条边。
三、填空题（30分）
1.写出头插法建立单链表的算法（5分）
2.求单源最短路径（从源点0开始），要求写出过程。（5分）
3.已知某二叉树的中序遍历序列：dfaechi
后序遍历序列：fdbehica
（1）请构造出该二叉树；（3分）
（2）写出前序遍历序列；（2分）
4.设查找的关键字序列{15,4,30,41,11,22,1}。画出对应的二叉排序树。（5分）
5.写出图的广度优先搜索算法（用邻接表存储）（5分）
6.线性表的关键字集合：
{19,14,23,01,68,20,84,27,55,11,10,79}已知散列函数为：H（k）=k%13，采用拉链法处理冲突，并设计出链表结构。（5分）
08数据结构（50分）
一、单项选择题（10分，每题1分）
1.若一个栈的输入序列为1，2，3，…，n，输出序列的第一个元素是i，则第i个输出元素是（）
A．i-j-1 B.i-j C.j-i+1 D.不确定的
2.循环队列存储在数组A[0..m]中，则入队的操作为（）
A.rear=rear+1
B.rear=(rear+1)mod(m-1)
C.rear=(rear+1)mod m
D.rear=(rear+1)mod(m+1)
3.二维数组A的每个元素是由6个字符组成的串，其行下表i=0，1，…，8，列下表j=1,2，…，10。若A按行序为主序存储，元素A[8][5]的起始地址与当A按列序为主序存储时的元素_________的起始地址相同。（设每个字符占一个字节）（）
A.A[8][5]
B.A[3][10]
C.A[5][8]
D.A[0][9]
4.下面说法不正确的是（）
A.广义表的表头总是一个广义表
B.广义表的表尾总是一个广义表
C.广义表难以用顺序存储结构
D.广义表可以是一个多层次的结构
5.算术表达式A+B*C-D/E转为前缀表达式后为（）
A.-A*C/DE
B.-A+B*CD/E
C.-+ABC/DE
D.-+A*BC/DE
6.有n个叶子的哈夫曼树的结点总数为（）
A.不确定
B.2n
C.2n+1
D.2n-1
7. 若X是中序线索二叉树中一个有左孩子的结点，且X不为根，则X的前驱为（）
A.X的双亲
B.X的右子树中最左的结点
C.X的左子树中最右结点
D.X的左子树中最右叶结点
8.无向图G=（V，E），其中V={a，b，c，d，e，f}，E={{a，b}，{a，e}，{a，c}，{b，e}，{c，f}，{f，d}，{e，d}}，对该图进行广度优先遍历，得到的顶点序列正确的是（）
A.a，b，e，c，d，f
B.a，c，f，e，b，d
C.a，e，b，c，f，d
D.a，e，d，f，c，b
9.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行_________探测。（）
A.k-1次
B.k次
C.k+1次
D.k（k+1）/2次
10.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是（）
A.直接插入排序
B.快速排序
C.直接选择排序
D.堆排序
二、填空题（5分，每题1分）
1.在有序表A[1..12]中，采用折半查找算法查等于A[12]的元素，所比较的元素下标依次为_____________________________。
2.求图的最小生成树有两种算法，________________ 算法适合于求稀疏图的最小生成树。
3.一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为_____________。
4.在单链表L中，指针p所指结点有后继结点的条件是________________________。
5.一个深度为k，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依次对结点编号，则编号是i的结点所在的层次号是_______________________（跟所在的层次号规定为1层）。
三、判断题（5分，每题1分）
1.链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高。（）
2.对一棵二叉树进行层次遍历时，应借助于一个栈。（）
3.将一棵树转成二叉树，跟节点没有左子树。（）
4.一个有向图的邻接表和逆邻接表中结点的个数可能不等。（）
5.在待排序数据有序的情况下，快速排序效果好。（）
四、应用题（20分，每题5分）
1.用集合{46，88，45，39，70，58，101，10，66，34}建立一棵二叉排序树，画出该树，并求在等概率情况下的平均查找长度。
2.设一组关键字{9，01，23，14，55，20，84，27}，采用哈希函数：H（key）=key
mod 7和二次探测再散列法解决冲突，对该关键字序列构造表长为10的哈希表。
3.假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07、0.19、0.02、0.06、0.32、0.03、0.21、0.10，试为这8个数字设计哈夫曼编码。
4.用普里姆算法构造下图的一棵最小生成树，并给出选点顺序。（以①为起点）
五、算法设计题（10分）
编写一个算法来交换单链表中指针P所指接点与其后继结点，HEAD是该链表的头结点，P 指向该链表中的某一结点。
山东省2008年普通高等教育专升本统一考试
数据结构（50分）
一、单项选择题（10分，每题1分）
1. 【答案】D
【解析】栈的基本性质是后进先出，本题中，在输出序列第一个元素是i时，只能确定1-i-1这些元素的输出的先后次序，但是不能确定出第i个元素具体输出哪个元素。
2. 【答案】D
【解析】在循环队列中，rear指针指示队尾，本题中存储数组实质上为A[m+1]。所以，入队列的操作应该是修改rear=(rear+1)%(m+1),答案Ｃ是错误的。
3. 【答案】B
【解析】本题中二维数组属于9行10列。所以，首先确定以行序为主序的存储中，A[8][5]在所有元素排列中的位置为第85位，同样的确定以列序为主序的第85个存储元素的元素应该为A[3][10]。
4. 【答案】A
【解析】构成广义表的数据元素可以是单个元素，也可以是广义表。广义表的表头就是广义表中的第一个元素，可以是单个元素，也可以是子表。选项B、C、D都是正确的。
5. 【答案】D
【解析】在算数表达式的前缀表达式实质上就是运算符写在两个运算数的前面，当然在实现转换时，要考虑运算数的相对位置不变，而且考虑运算的优先级问题。当然，也可以采用二叉树表示出算数表达式，这样，前序遍历顺序即为前缀表达式（波兰式），后序遍历即位后缀表达式（逆波兰式），本题答案选D。
6. 【答案】D
【解析】哈夫曼树的特点是没有度为1的结点，根据二叉树的性质3，n0=n2+1，所以，具有n个叶子结点的二叉树具有n-1个度为２的结点，因此，答案选Ｄ。
7. 【答案】C
【解析】因为在中序线索二叉树中，结点X有左子树，所以，该结点前驱在左子树中，左子树中最右的结点是子树中最后一个遍历的结点，该结点可能为叶子结点，也可能是度为
1的结点（即有左孩子）。
8. 【答案】A
【解析】根据本题无向图的定义，可以图G
根据广度优先遍历的算法思想，可以确定A是正确的，选项B、C、D都是错误的。
9. 【答案】D
【解析】采取线性探测法存储这k个同义词，则第一个关键字可以直接存储，其余的k-1个元素中，理想的情况下，第１个元素探测１次可以存储，第２个元素探测２次才能存储，以此类推，因此，至少需要探测的次数为k(k+1)/2。
10. 【答案】B
【解析】直接插入排序的算法思想是从第2到最后一个元素，依次插入到前面的有序序列中，因此，每趟执行结束，不能确定出一个元素最终的位置；快速排序的每趟可以确定出枢轴元素的最终位置，而且，当元素基本有序时，其排序性能会降低，所以选B。选项C、D能符合第一条要求，但是其时间性能跟待排元素的序列无关。
二、填空题（本大题共10小题，每小题1分，共10分）
1. 【答案】6、9、11、12
【解析】根据有序表的折半查找的mid的取值为(low+high)/2，可以确定判定树的形态如下，
查找下标为12的元素时，先后要与下标为：6、9、11、
12四个元素进行比较。
2．【答案】克鲁斯卡尔（Kruskal）
【解析】求解最小生成树的算法主要有两种，普里姆算法（Prim）时间复杂度为O（n2）,与网中的边数无关，因此适合于求边稠密的网的最小生成树；而克鲁斯卡尔（Kruskal）算法时间复杂度为O（eloge），因此，适合于求边稀疏的网的最小生成树。
3. 【答案】2
【解析】左子树为空，则根结点没有前驱，左孩子指针域为空，另外，根结点右子树中最后一个结点没有后继，右孩子指针域也为空，所以，该二叉树中空链域的个数为2。
4. 【答案】p->next!=NULL（或文字说明“指针P所指结点的指针域不等于NULL”）
【解析】在单链表L中，指针p所指结点有后继，前提是指针P所指结点的指针域不等于NULL，如果指针域默认为next，则可以表示为“p->next!=NULL”。（注：NULL一定是大写）
５．【答案】??1 log
2
+
i
【解析】深度为K的结点已经构成完全二叉树，所以前i个结点也为完全二叉树，所以根
据性质4可以确定第i个结点的深度为??1 log
2
+
i
。
三、判断题（5分，每题1分）
1．【答案】√
【解析】链式存储结构的线性表的优点就在于实现插入和删除操作时，不需要大量元素的移动，因此，比顺序存储结构中实现插入删除操作效率高。
2．【答案】×
【解析】实现二叉树的按层遍历时，应借助于一个队列作为辅助结构。
3．【答案】√
【解析】树转换为二叉树是依据的孩子兄弟表示法这种存储结构，树根没有兄弟，所以，一棵树转换成二叉树，对应二叉树根结点没有左子树。
4．【答案】×
【解析】有向图的邻接表中结点的个数与逆邻接表中结点的个数是相等的，都等于图中所有顶点的入度和（或出度和）的值。
5．【答案】×
【解析】就平均时间而言，快速排序目前被认为是最好的一种内部排序方法，但是，当待排序列基本有序时，快速排序将蜕化为冒泡排序，因此，排序效果反而降低。
四、综合应用题（本大题共3小题，每小题5分，共15分）
1．答：根据结点画出二叉排序的过程如图所示：
等概率情况下，平均查找长度为：（5*2+4*2+3*3+2*2+1*1）/10=3.2
2．答：根据哈希函数和处理冲突的方法为二次探测再散列，构造哈希表如图所示：0123456789
【解析】注意关键字的顺序,9%7=2; 1%7=1; 23%7=2,冲突,但是(2+12)%10=3;14%7=0;
55%7=6;20%7=6,冲突,但是(6+12)%10=7;84%7=0,冲突,但是(0+12)%10=1,已经占用,由于函数值已经是0了，在这里不能再试探-12,因此(0+22)%10=4,所以84存储在下标4的单元格内。最后27%7=6，冲突，
(6+12)%10=7，仍然冲突，（6-12)%10=5，所以27存储在下标5的单元格内。
3．答：根据每个字符出现的频率，我们可以求解哈夫曼树，为方便求解，不妨将频率变为整数，则权值分别为：7，19，2，6，32，3，21，10，由此构造哈夫曼如图：
由此可以设定每个字符的哈夫曼编码：0.02：00000； 0.03:00001; 0.06:0001;
0.07:0010; 0.1:0011; 0.32:01; 0.19:10; 0.21:11。
4.答:根据普里姆算法构造最小生成树,如下图所示:
五、算法设计（本大题共１小题，共10分）
答：Linklist exchange(Linklist &head,Linklist p)
{ q=head->next;
pre=head; //初始化q、pre指针，当q指针移动到与P指针相等时，则pre指针正好指向前
驱结点;
while(q!=NULL&&q!=p) {pre=q;q=q->next;}
if(p->next==NULL) printf(“p无后继结点\n”);
else { q=p->next; //利用q、pre、p三个指针联合实现当前结点与前驱结点的交换; pre->next=q;
p->next=q->next;
q->next=p;
}
}
山东省2007年普通高等教育专升本统一考试
计算机科学与技术专业综合二试卷参考答案
数据结构（50分）
一、单选题（每小题1分，共10分，）
1. 【答案】C
【解析】具有三个结点的二叉树的形态共有5种，而具有三个结点的树的形态是2种。
2. 【答案】C
【解析】若输出的第一个元素为n，则所有元素均已经入栈，所以出栈顺序即为元素的逆
序排列，因此，输出的第i个元素的值为n-i+1。
3. 【答案】A
【解析】根据树与二叉树的相互转换数关系，以及树及二叉树的遍历顺序，有以下结论：（1）树的先根遍历顺序与对应二叉树的先序遍历顺序相同；（2）树的后根遍历顺序与对
应二叉树的中序遍历顺序相同。
4. 【答案】D
【解析】算法的时间性能的评价主要使用算法的时间复杂度，算法的空间性能的评价主要
采用空间复杂度。
5. 【答案】A
【解析】线性表的顺序存储结构要求分配连续的存储空间，因此，可以实现数据元素的顺
序存取以及随机存取。但元素的插入和删除需要涉及大量元素的移动；而线性表的链式存储方便于元素的插入与删除，但是不能实现随机存取，只能进行顺序存取。
6. 【答案】D
【解析】顺序表要求存储空间是连续，所以，只要知道基地址，知道每个元素所占的字节数，就可以求每个元素的存储起始地址。
7. 【答案】D
【解析】在中序线索二叉树中，若某结点有右子树，则在访问完该结点后要访问右子树中最左边的结点，所以答案选D。
8. 【答案】C
【解析】栈的基本性质是后进先出，在入栈序列为abcde，出栈的第一个元素为d时，则
已经入栈，所以，此时“abc”三个元素的出栈序列中，一定是cba的顺序，而不能出现cab的顺序，所以选项C是错误的。
9. 【答案】A
【解析】构成广义表的数据元素可以单个元素，也可以是由若干个元素所组成的子表。广义表属于特殊的线性表，特殊的地方在于广义表的元素中能否使用子表。
10. 【答案】B
【解析】根据二叉树的基本性质3，对于任意一棵二叉树，满足度为0的结点为度为2的结点数加1。所以，答案选B
二、填空题（本大题共10小题，每小题1分，共10分）
1. 【答案】一定相邻
【解析】顺序表采用连续存储空间作为元素的存储结构，所以，逻辑上相邻的数据元的物理存储空间也一定相邻。
2．【答案】块
【解析】在索引顺序表中，将所有的关键字进行分块，块与块之间关键字大小有序，在每个块内部元素排列无序，可以把每个组中最大元素值作为该组的索引加入到索引表中排列，所以，索引表中元素排列是有序的，因此，在查找元素时，先查找索引表，获得查找元素所在组后，再使用顺序查找去查找相应的块。
3. 【答案】分配和收集
【解析】分配法排序属于一种典型的多关键字排序，分配排序的基本思想是排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。
4. 【答案】入度
【解析】拓扑排序每次都选择没有前驱的结点进行输出，其中结点没有前驱，即入度为0。5．【答案】n+1
【解析】二叉链表中，每个结点有2个指针域，具有n个结点的二叉链表一共有2n个指针域，其中，除根结点外，每个结点需要一个指针来指向，所以空的指针域的个数为n+1。
6.【答案】出度
【解析】有向图的邻接表是指:所有顶点建立顶点结点，以每个顶点为弧尾的所有弧对应的另外一个顶点序号构成表结点链接形成的单链表。所以，通过计数每个单链表中表结点的
个数，可以计算每个顶点的出度。
7．【答案】列
【解析】有向图的邻接矩阵的特点是，通过求解每一行上1的个数，可以求解每个顶点的出度；通过求解每一列上1的个数，可以求解每个顶点的出度。无向图的邻接矩阵属于对称矩阵，每个顶点的度即为行或列上1的个个数。
8.【答案】双亲
【解析】树的表示方法一共有三种，双亲表示法、孩子表示法以及孩子兄弟表示法。其中双亲表示法为每个树中元素建立一个结点，包括存储数据元素本身，以及该结点的双亲结点的存储下标，所以，该存储方法可以很容易的求解结点的双亲以及祖先，但是求解结点的孩子及后代需要遍历整个数组。
9．【答案】67。
。图为五个权值形成的哈夫曼树，树的带权路径长度为：(2+3)*4+5*3+9*2+14*1=67
10. 【答案】n(n-1)
【解析】在有n个顶点的有向完全图中，从每个顶点出去的弧有n-1条，所以总弧数为n(n-1)。
四、综合题（30分，每题5分）
1．答：viod creat(Linklist &L)
{ L=(Linklist)malloc(sizeof(Lnode));
L->next=NULL;
for(i=n;i>0;i++)
{ p=(Linklist)malloc(sizeof(Lnode));
scanf(&p->data);
p->next=L->next;
L->next=p;
}
} 注意：除了使用头插法，还有尾插法，可以查阅资料写出算法。
2．答：
3．答：根据（1）中序遍历的特点：左子树、根、右子树的遍历顺序；（2）后序遍历的特点：左子树、右子树、根；（3）二叉树的每棵子树也符合该特性。所以，该二叉树的构造过程为:
由此可得到二叉树的前序遍历顺序为：abdfceih
4．答：根据二叉排序树的定义，创建过程如下图：
5. 答：
该邻接表的结构描述如下：
#define VERTEX_MAX 100
typedef struct node
{int adjvex;
struct node *next;
}Edgenode; //表结点的类型定义
typedef struct vnode
{vextype vertex;
Edgenode *firstedge;
}VertexNode; //顶点结点的类型定义
Typedef struct
{ VertexNode adjlist[VERTEX_MAX];
int n,e; //顶点数和边数
}ALGraph; //邻接表的类型定义
void BFS(ALGraph *G) {
for(v=0;v
InitQueue(Q)；
for(v=0;v
if(!visited[v])
{visited[v]=TURE;
Printf(“%c”,G->adjlist[v].vertex);
EnQueue(Q,v)
while(!QueueEmpty(Q)) {
DeQueue(Q，u)；
for(p=G->adjlist[u].firstedge;p;p=p->next)
if(!visited[p->adjvex])
{ visited[p->adjvex]=TRUE;
Printf(“%c”,G->adjlist[p->adjvex].vertex); EnQueue(Q,p->adjvex);
}
}
}
}
6．答：根据哈希函数以及拉链法解决冲突，构造如下哈希表：
1
2
3
4
5
6
7
8
9
10
11
12
山东省2006年普通高等教育专升本统一考试
数据结构（50分）
一、单选题（每小题1分，共10分，）
1. 【答案】D
【解析】所有能输入到计算机中的符号的总称为数据，数据元素是构成数据的基本单位，数据元素可以由若干条记录组成，每条记录又可由若干数据项组成。相同性质的数据元素的集合构成数据对象。数据元素的类型称为数据类型。
2. 【答案】B
【解析】采用顺序存储结构的线性表在进程插入和删除元素时需要涉及大量元素的移动问题。而链式存储结构可以很容易的实现插入和删除操作，因此选B。
3. 【答案】D
【解析】如果9作为第一个出栈元素，前提是3，5，7已经依次入栈了，所以，此时输出顺序只能为9，7，5，3。选项D是错误的。
4. 【答案】D
【解析】字符串的长度应该是串中所有包含的字符的个数，所以选项A只提到了字母，选项B提到了不同字符的个数，均是错误的，每个字符串都属于自己的子串，因此选项C错误。
5. 【答案】D
【解析】广义表的表头是广义表中的头元素，广义表的表尾是指除去表头元素，其余元素所组成的广义表，因此，答案选D而不是C，更不是A和B。
6. 【答案】A
【解析】图的生成树是指包含图中所有的n个顶点，但仅包含连通这个n个顶点的n-1条边。
7. 【答案】C
【解析】根据二叉树的基本性质3：对于任意一棵二叉树满足n0=n2+1，所以，当度为2的结点数为8时，叶子结点个数为9。
8. 【答案】A
【解析】在二叉链表中每个结点有两个指针域，而除了根结点外，每个结点均需要占用其中一个指针域，所以空的指针域个数为：2*n-(n-1)=n+1个。
9. 【答案】C
【解析】在等概率的情况下，每个元素的查找概率都是1/n，其中查找最后一个元素需要比较1次，查找第n-1个结点需要比较2次，依次类推，查找第1个结点需要比较n次，平均查找长度为：（1+2+3+…）/n=(n+1)/2。
10. 【答案】A
【解析】对含有n个元素的线性表，执行选择排序时，无论序列的初始排列如何，均需要进行n-1趟排序，每次都需要n-i次比较，确定出第i个位置上的元素来，所以答案选A。而插入排序、冒泡排序当元素已经有序时，比较次数可以降低为n-1次；快速排序当元素排列基本有序时，性能反而降低。
二、填空题（本大题共10小题，每小题1分，共10分）
1. 【答案】f==r
【解析】在循环队列中，分别用f指示队头，r指向队尾。所以当f==r时，表示队列中没有元素存在，通常当(r+1)%maxsize==f时，表示该循环队列已满。（以牺牲一个存储空间伟代价）。在此注意是“＝＝”，而不是“＝”。
2．【答案】1/2
【解析】假设在长度为n的顺序表中插入元素时，插入位置有n+1个，平均需要移动元素数量为（0＋1＋2…+n）/(n+1)=n/2；当删除元素时，删除位置有n个，平均需要移动的元素个数为：（0＋1＋2＋…+(n-1)）/n=(n-1)/2。都接近1/2的元素个数。
3. 【答案】38
【解析】二位数组每行中有5个元素，每个元素占2个字节，因此LOC（3,2）=LOC(0,0)+(3*4+2)*2=38
4. 【答案】2K -1
【解析】二叉树的基本性质２。
5．【答案】e
【解析】有向图的邻接表是以图中所有顶点作为头结点，将所有以该顶点为弧尾的弧生成表结点构成的。所以，表结点数与弧数是一一对应的。
6.【答案】中序
【解析】二叉排序树中所有左子树中结点均比根结点的值小，所以右子树中结点值均比根结点的值大，如果左右子树不空，左右子树都满足该特性，所以二叉排序树的中序遍历顺序是由小到大的顺序排列的。
7．【答案】2
【解析】无论在有向图还是在无向图中，每条边或弧在计算顶点的度时均被用过２次，所以，得到的顶点的度的和就是边数的２倍。
8.【答案】3
【解析】该有序表中包含７个元素，因此先与第４个元素进行比较，然后和第２个元素进行比较，最后和第３个元素进行比较，所以共需要比较３次成功。
9．【答案】9
【解析】根据哈希函数求得函数值为５，查找发现冲突，根据二次探测再散列，分别将函数值+1２、-1２、+2２、-2２…，并对表长进行取余，进行试探。所以答案填9。
10. 【答案】n(n-1)/2
【解析】在有n个顶点的无向完全图中，从每个顶点出去的边有n-1条边，但每条边被用过2次，所以总边数为n(n-1)/2。
三、判断题（本大题共5小题，每小题1分，共5分）
1．【答案】×
【解析】算法的特性包含确定性。确定性就是指每条指令必须是确定的含义，不能产生二义性，并且，在任何条件下，算法只有唯一的一条执行路径，即对相同的输入只能得出相同的输出。
2．【答案】×
【解析】线性表的链式存储结构的存储单元地址不要求连续，但是可以连续；而线性表的顺序存储结构一定要求分配连续的存储单元。
3．【答案】√
【解析】队列属于特殊的线性表，要求在表的一端进行插入，在表的另一端进程删除，能够插入的一端称为队尾，能够删除的一端称为对头。
4．【答案】×
【解析】内部排序指的是待排记录存放在计算机随机存储器中进行的排序过程，外部排序指的是待排记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。拓扑排序不属于内部排序。
5．【答案】√
【解析】一棵树转化为二叉树，其根结点一定没有右孩子，即该二叉树没有右子树。只有2棵及以上的非空树组成的森林转化为二叉树，才能使得对应二叉树有右子树。
四、综合应用题（本大题共3小题，每小题5分，共15分）
1．答：具有三个结点的二叉树共有5种基本形态，具体如下图所示：
2．答：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1
1
1
1
1
1
1
1
1
1
如图为该图的邻接矩阵。从V1出发的深度优先遍历顺序为
V1→V4→V5→V2→V3或V1→V2→V5→V4→V3或V1→V3→V2→V5→V4或V1→V3→V4→V5→V2
3．答：树转换为二叉树为：其中该二叉树的先序遍历顺序为A，B，C，E，F，G，D
五、算法设计（本大题共１小题，共10分）
答：Linklist delete(Linklist &L,Elemtype x)
{ Linklist p,q;
q=L; p=L->next; //初始化p指向第一个结点，q始终指向p结点的前驱；while(p!=NULL)
{ if(p->data==x) //找到符合条件的结点；
{q->next=p->next;
free(p);
p=q->next; //删除该结点，并修改p指针；
}
else
{q=p;
p=p->next; //先使q后移，p向后移动。
}
}
}
06C语言程序设计（50分）
六、单选题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填写在题干后面的括号内。每小题1分，共15分）
1.C语言程序的基本单位是（）
A.程序行
B.语句
C.函数
D.字符
2.可用作C语言用户标识符的一组字符串是（）
A.void define WORD
B.a3_b3 _123 IF
C.For –abc Case
D.2a DO sizeof
3.设int a=12，则执行完语句a+=a-=a*a后，a的值是（）
A.552
B.264
C.144
D.-264
4.以下叙述正确的是（）
A.do-while语句构成的循环不能用其它语句构成的循环来代替。
B. do-while语句构成的循环只能用break语句退出。
C.用do-while语句构成的循环，在while后的表达式为非零时结束循环。
D.用do-while语句构成的循环，在while后的表达式为零时结束循环。
5.设有说明int（*ptr）[10]其中的标识符ptr是（）
A.10个执行整型变量的指针
B.指向10个整型变量函数指针
C.一个指向具有10个整型元素的一维数组的指针
D.具有10个指针元素的一维指针数组，每个元素都只能指向整型量
6.有以下程序段
typedef struct NODE{
int num;
struct NODE *next;
}OLD;
则以下叙述中正确的是（）
A.以上的说明形式非法
B.NODE是一个结构体类型
C.OLD是一个结构体类型
D.OLD是一个结构体变量
7.以下不能正确计算代数式值的C语言表达式是（）
A.1/3*sin(1/2)*sin(1/2)
B.sin(0.5)*sin(0.5)/3
C.pow(sin(0.5),2)/3
D.1/3.0*pow(sin(1.0/2),2)
8.C语言规定，程序中各函数之间（）
A.既允许直接递归调用也允许间接递归调用
B.不允许直接递归调用也不允许间接递归调用
C.允许直接递归调用不允许间接递归调用
D.不允许直接递归调用允许间接递归调用
9.在宏定义#define PI 3.14159中，用宏名PI代替一个（）
A.单精度数
B.双精度数
C.常量
D.字符串
10.在C语言中，要求运算数必须是整型的运算符是（）
A.%
B./
C.<
D.!
11.为表示关系x≥y≥z，应使用的C语言表达式是（）
A.(x>=y)&&(y>=z)
B.(x>=y)AND(y>=z)
C.(x>=y>=z)
D.(x>=y)&(y>=z)
12.有以下程序段
int k=0,a=3,b=4,c=5;k=a>c?c:k;
执行该程序段后，k的值是（）
A.3
B.2
C.1
D.0
13.若定义char *s="\\"Name\\Address\n"，则指针s所指字符串的长度为（）
A.19
B.15
C.18
D.说明不合法
14.下述对C语言字符数组的描述中错误的是（）
A.字符数组可以存放字符串
B.字符数组中的字符串可以整体输入、输出
C.可以在赋值语句中通过赋值运算符对字符数组整体赋值
D.不可以用关系运算符对字符数组中的字符串进行比较
15.设有如下的函数
exam(float x){
printf("\n%f",x*x);
}
则函数的类型为（）
A.与参数x的类型相同
B.是void
C.是int
D.无法确定
七、阅读下列程序，写出其运行结果（每小题5分，共25分）
1、程序：
main()
{ int i,j,x;
for(i=1;i<=4;i++)
{for(j=1;j<=4-i;j++)
printf(" ");
for(j=0;j<=2*i+1;j++)
printf("*");
printf("\n");
}
}
答案：
2、程序：
main()
{ int k=3,n=0;
一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。
数据结构复习题 第一章概论 一、选择题 1、研究数据结构就是研究( D )。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是( A )。 A. 空间复杂度和时间复杂度 B. 正确性和简单性C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是( D )。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C )。 fori0;im;i++ forj0;jn;j++ a[i][j]i*j; A. Om2 B. On2 C. Om*n D. Om+n 6、算法是( D )。
A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示( C )。 A. On B. Onlog2n C. On2 D. Olog2n 8、下面程序段的时间复杂度为( C )。 i1; whilein ii*3; A. On B. O3n C. Olog3n D. On3 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( B )和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是( A )。 is0; whilesn i++;s+i; A. On B. On2 C. Olog2n D. On3 11、抽象数据类型的三个组成部分分别为( A )。 A. 数据对象、数据关系和基本操作 B. 数据元素、逻辑结构和存储结构 C. 数据项、数据元素和数据类型 D. 数据元素、数据结构和数据类型 12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是(D)。
中国矿业大学2011-2012学年 《数据结构》试卷（A卷）（考试时间：100分钟） 一. 填空（每空2分，共40分） 1. 数据结构式具有相同性质的数据元素的（1）。 2. 通常程序在调用另一个程序时，都需要使用一个（2）来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。 3. 有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为__（3）_____,_____(4)____。 4. 完全二叉树第4 个节点的父节点是第 (5) 节点，左孩子是第 (6) 个节点。如果该二叉树有10层，则共有 (7) 个节点。 5. 请描述在循环队列Q中，队头和队尾指针分别由front和rear表示，该队列有10个存储空间，判断队空和队满的条件分别分：_____(8)________,_______(9)_________。 6. 字符串t=”child”，s=”cake”，请写出下列函数的结果：StrLength(t) =（10）__;Concat(SubString(s,3,1)，SubString(t,2,2))=____（11）___。 7. 一棵二叉树为 则后序序列为（12），中序序列为（13），先序序列为__（14）____。 8. 请用数据序列{53，17，12，66，58，70，87，25，56，60 }构造一棵二叉排序树_(15）_。 9.。一个栈输入的序列式1,2,3，则可能的且以2为开头的输出序列是 (16) ，不可能的序列是____（17）____。 10. 有n个结点的无向完全图的边数分别为_______(18)_______。 11. 要从数据：2，3，4，8，9，11，13查找11，若采用折半查找法，则在（19）次比较后，才找到该数据。 12. 在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下（20）_____最快。 二简答题： 1给定{15,3,14,2,6,9,16,17}，试为这8个数设计哈夫曼编码，并计算其带权路径长度。 2请对下图的无向带权图按克鲁斯卡尔算法求其最小生成树。（要求使用图画出每一步过程）。 C G E D F B H A
《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 、 1. 对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为 (c )。 (A)、正确性但).可行性(C).健壮性 2 ?设S为C语言的语句,计算机执行下面算法时， for(i=n-1 ; i>=0; i--) for(j=0 ; jvi; j++) (A)、n2(B). O(nlgn) 3?折半查找法适用于( a (D). 输入性 算法的时间复杂度为(d S； (C). O(n) (D). )。 O(n2) (A)、有序顺序表(B)、有序单链表 (C)、有序顺序表和有序单链表都可以 4 .顺序存储结构的优势是( d )。 (A)、利于插入操作(B)、利于删除操作 (C)、利于顺序访问(D)、利于随机访问 5. 深度为k的完全二叉树，其叶子结点必在第 (A)、k-1 ( B)、k (C)、k-1 和 6. 具有60个结点的二叉树，其叶子结点有 (A)、11 ( B)、13 ( C)、48 (D)、无限制 c )层上。 (D)、1 至 k 12个，则度过1 (D)、37 k 的结点数为( 7 .图的Depth-First Search(DFS) 遍历思想实际上是二叉树( 法的推广。 (A)、先序(B)、中序(C)、后序(D)、层序 8.在下列链队列Q中，元素a出队的操作序列为( a )遍历方 front (A )、 (B )、 (C)、 (D )、p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于( (A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和(B) 、 ) 所有结点权值之和 根结点的值 b ■
2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出
8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点
习 9解答 判断题： 1．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。 答：FALSE (错。链表表示的有序表不能用折半查找法。) 2.有n 个数据放在一维数组A[1..n]中，在进行顺序查找时，这n 个数的排列有序或无序其平均查找长度不同。 答：FALSE (错。因顺序查找既适合于有序表也适合于无序表；对这两种表，若对于每个元素的查找概率相等，则顺序查找的ASL 相同，并且都是(n+1)/2；对于查找概率不同的情况，则按查找概率由大到小排序的无序表其ASL 要比有序表的ASL 小。) 3.折半查找是先确定待查有序表记录的范围，然后逐步缩小范围，直到找到或找不到该记录为止。( ) 答：TRUE 4.哈希表的查找效率主要取决于哈希表哈希表造表时选取的哈希函数和处理冲突的方法。 答：TRUE 5.查找表是由同一类型的数据元素(或记录)构成的集合。 答：TRUE 单选题： 6.对于18个元素的有序表采用二分(折半)查找，则查找A[3]的比较序列的下标为( )。 A. 1、2、3 B. 9、5、2、3 C. 9、5、3 D.9、4、2、3 答：D (第一次??2/)181(+ = 9,第二次??2/)81(+ = 4，第三次??2/)31(+ = 2, (第四次??2/)33(+ = 3，故选D. 7. 顺序查找法适合于存储结构为____________的线性表。 A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 答：B 8.对线性表进行二分查找时，要求线性表必须( )。 A ．以顺序方式存储 B. 以链接方式存储 C ．以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序 答：C 9.设哈希表长m=14，哈希函数为H(k) = k MOD 11。表中已有4个记录(如下图
计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编6 (总分：60.00，做题时间：90分钟) 一、单项选择题(总题数：14，分数：28.00) 1.为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )。【2009年 全国试题1(2)分】 A.栈 B.队列√ C.树 D.图 2.设栈S和队列Q的初始状态均为空，元素a，b，c，d,e,j,g=g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b，d，c，f，e，a，g，则栈S的容量至少是( )。【2009年全国试题2(2)分】 A.1 B.2 C.3 √ D.4 按元素出队顺序计算栈的容量。b进栈时栈中有a，b出栈，cd进栈，栈中有acd，dc出栈，ef进栈，栈 中有aef,fea出栈，栈空，g进栈后出栈。所以栈S的容量至少是3。 3.若元素a，b，c，d,e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是( )。【2010年全国试题1(2)分】 A.d,c，e，b，f,a B.c，b，d,a，e，f C.b，c，a，e，f，d D.a,f，e,d,c，b √ 4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a，b，c，d，e依次入此队列后再进行出队操作，则不可能得到的出队序列是( )。【2010年全国试题2(2)分】 A.b，a，c，d, e B.d,b，a，c，e C.d，b,c，a，e √ D.e，c，b，a，d a先入队，b和c可在a的任一端入队，选项A、B、D都符合要求，只有选项C不可能出现。双端队列出队结果的分析可参见四、36。 5.元素a，b，c，d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是( )。【2011年全国试题2(2)分】 A.3 B.4 √ C.5 D.6 元素d进栈时，元素a，b，c已在栈中，d出栈后，P可以在a，b，c任一元素的前面进栈并出栈，也可以在元素a后出栈，c，b，a必须依次出栈，所以元素d开头的序列个数是4。 6.已知循环队列存储在一维数组A[0．n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是( )。[2011年全国试题3(2)分】 A.0，0 B.0，n—1 √ C.n一1，0
四川大学期末考试试题 （2008-2009学年第1学期） 课程号：课程名称：数据结构与算法分析（B卷）任课教师： 1．数据类型为（）。 A）数据项的集合B）值的集合及定义在其上的一组操作的总称 C）数据元素的集合D）关键字的集合 2．链表不具有的特点是（）。 A）可随机直接访问任一元素B）插入删除不需要移动元素 C）不必事先估计元素个数D）所需空间与线性表长度成正比 3．设一个栈的入栈序列是ABCD，则借助于一个栈所得到的出栈序列不可能是（）。 A）ABCD B）DCBA C）ABCD D）DABC 4．将对称矩阵A nxn压缩存储在一维数组B[m]中，则m的值至少为（）。 A）n(n+1)/2 B）n(n-1)/2 C）n(n+1) D）n2 5．设二叉树中有n2个度为2的结点，n1个度为1的结点，n0个叶子结点，则此二叉树中空指针域个数为（）。 A）n0+n1+n2 B）n2+n1+2n0 C）2n2+n1D）2n0+n1 6．对于具有n个顶点的强连图，其弧条数的最小值为（）。 A）n+1 B）n C）n-1 D）n-2 7．一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（）个结点。 A）2k-1-1 B）2k-1C）2k-1+1 D）2k-1 8．归并排序的时间复杂度是（）。 A）O(1) B）O(n) C）O(n2) D）O(nlogn) 9．每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（）。 A）冒泡排序B）简单选择排序C）希尔排序D）直接插入排序10．按照二叉树的定义，具有3个结点的不同形态（相似）的二叉树有（）种。 A）3 B）4 C）5 D）6 二、（本题10分） 利用两个栈S1、S2模拟一个队列（如客户队列）时，如何用栈的运算实现队列的插入、删除运算，请简述算法思想。 三、（本题10分） 已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。 先序序列：ABCDEFGH IJ 中序序列：CBEDAGHFJI 注：试题字迹务必清晰，书写工整。本题2页，本页为第1页 教务处试题编号：
计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 6 (总分：88.00，做题时间：90分钟) 一、单项选择题(总题数：33，分数：66.00) 1.一棵完全二叉树又是一棵( )。【华中科技大学2006一、7(2分)】 A.平衡二叉树 B.堆√ C.二叉排序树 D.哈夫曼(Huffman)树 完全二叉树的叶子至多在下面两层上，且一个结点若无左子树，绝不能有右子树。平衡二叉树任何结点的左右子树的高度差的绝对值不超过1，但其结点的值符合二叉排序树的定义。平衡二叉树(包括二叉排序树)的树形不一定是完全二叉树。堆是一个序列，有大堆和小堆，编号为i的结点，其父结点、左右子女结点之间位置的关系，符合完全二叉树父结点、左右子女结点之间的关系，从这点上说，可以把堆看成完全二叉树。哈夫曼树是二叉树，但树形不一定满足完全二叉树的定义。 2.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是( )。【合肥工业大学1999一、5(2分)】 A.不确定 B.0 C.1 D.2 √ 左子树为空的二叉树的根结点的左线索为空(无前驱)，先序序列的最后结点的右线索为空(无后继)，共2个空链域。 3.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。【合肥工业大学2000一、5(2分)】 A.0 B.1 √ C.2 D.不确定 4.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为( )。【南京理工大学1996 一、6(2分)】 A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点√ D.X的左子树中最右叶结点 5.引入二叉线索树的目的是( )。【南京理工大学1998一、5(2分)】 A.加快查找结点的前驱或后继的速度√ B.为了能在二叉树中方便地进行插入与删除 C.为了能方便地找到双亲 D.使二叉树的遍历结果唯一 6.线素二叉树是一种( )结构。【西安电子科技大学1996一、9(2分)】 A.逻辑 B.逻辑和存储 C.物理√ D.线性 7.甩个结点的线索二叉树上含有的线索数为( )。【中山大学1998二、8(2分)】
《数据结构》试题参考答案 （开卷） （电信系本科2001级 2002年12月） 一、回答下列问题 (每题4分，共36分) 1. 某完全二叉树共有15381个结点，请问其树叶有多少个？ 答：n2=?n/2?=?15381/2?=7691(个) 2. 假设有二维数组A 7×9，每个元素用相邻的6个字节存储，存储器按字节编址。已知A 的起始存储位置（基地址）为1000，末尾元素A[6][8]的第一个字节地址为多少？若按列存储时，元素A[4][7]的第一个字节地址为多少？ 答：① 末尾元素A[6][8]的第一个字节地址＝1000＋（7行×9列—1）×6B ＝1000＋62×6=1372 ②按列存储时，元素A[4][7]的第一个字节地址＝1000＋（7列×7行＋4）×6B ＝1000＋53×6=1318 3. 在KMP 算法中，已知模式串为ADABBADADA ，请写出模式串的next[j]函数值。 答：根据 0 当j ＝1时 next[ j ]＝ max { k |1 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】4．一个算法应该是（）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] 数据结构试卷（一） 一、选择题（20分） 1．组成数据的基本单位是（）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4， 1>}，则数据结构A是（）。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3．数组的逻辑结构不同于下列（）的逻辑结构。 (A) 线性表(B) 栈(C) 队列(D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（）个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（）。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（）。 (A) 6 (B) 4 (C) 3 (D) 2 7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）。 (A) 100 (B) 40 (C) 55 (D) 80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（）。 (A) 3 (B) 4 (C) 5 (D) 1 9．根据二叉树的定义可知二叉树共有（）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法，则（）的空间复杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序 二、填空题(30分) 1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向 当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。 2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为 ___________，在链式存储结构上实现顺序查找的平均时间复杂度为___________。 3.设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有 ________个指针域，__________个空指针域。 4.设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后 面插入结点B的操作序列为______________________________________。 5.设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和 _________个表结点。 6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。 2005年－2006学年第二学期“数据结构”考试试题（A） 姓名学号(序号)_ 答案隐藏班号 要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。 一、单项选择题（每小题2分，共20分） 1．数据的运算a 。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 答：A。 2. 链表不具备的特点是 a 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 答：参见本节要点3。本题答案为：A。 3. 在顺序表中删除一个元素的时间复杂度为 c 。 A.O(1) B.O(log2n) C.O(n) D.O(n2) 答：C。 4．以下线性表的存储结构中具有随机存取功能的是 d 。 A. 不带头结点的单链表 B. 带头结点的单链表 C. 循环双链表 D. 顺序表 解 D。 5. 一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。 A.edcba B.decba C.dceab D.abcde 答：C。 6. 循环队列qu的队空条件是 d 。 A. (qu.rear+1)%MaxSize==(qu.front+1)%MaxSize B. (qu.rear+1)%MaxSize==qu.front+1 C.(qu.rear+1)%MaxSize==qu.front D.qu.rear==qu.front 答：D。 7. 两个串相等必有串长度相等且 b 。 A.串的各位置字符任意 B.串中各位置字符均对应相等 C.两个串含有相同的字符 D.两个所含字符任意 答：B。 8. 用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是c 。 A.94,32,40,90,80,46,21,69 B.32,40,21,46,69,94,90, 80 C.21,32,46,40,80,69,90,94 D.90,69,80,46,21,32,94, 40 答：C。 9. 以下序列不是堆（大根或小根）的是 d 。 A.{100,85,98,77,80,60,82,40,20,10,66} B.{100,98,85,82,80, 77,66,60,40,20,10} C.{10,20,40,60,66,77,80,82,85,98,100} D.{100,85,40,77,80, 60,66,98,82,10,20} 数据结构模拟试题... 一、简答题（15分，每小题3分） 1.简要说明算法与程序的区别。 2.在哈希表中，发生冲突的可能性与哪些因素有关？为什么？ 3.说明在图的遍历中，设置访问标志数组的作用。 4.说明以下三个概念的关系：头指针，头结点，首元素结点。 5.在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？ 二、判断题（10分，每小题1分） 正确在括号内打√，错误打× ( )（1）广义表((( a ), b), c ) 的表头是(( a ), b)，表尾是( c )。 ( )（2）在哈夫曼树中，权值最小的结点离根结点最近。 ( )（3）基数排序是高位优先排序法。 ( )（4）在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。 ( )（5）在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：p->next = s; s->next = p->next; ( )（6）抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。 ( )（7）数组元素的下标值越大，存取时间越长。 ( )（8）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。 ( )（9）拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。 ( )（10）长度为1的串等价于一个字符型常量。 三、单项选择题（10分, 每小题1分） 1．排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？ A、堆排序 B、直接插入排序 C、快速排序 D、冒泡排序 2．已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该： A）将邻接矩阵的第i行删除B）将邻接矩阵的第i行元素全部置为0 C）将邻接矩阵的第i列删除D）将邻接矩阵的第i列元素全部置为0 3．有一个含头结点的双向循环链表，头指针为head, 则其为空的条件是： A.head->priro==NULL B. head->next==NULL C. head->next==head D. head->next-> priro==NULL 4. 在顺序表( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值11，所需的关键码比 第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i 《数据结构》试题（100分） （供2005级信息管理与信息系统本科专业使用） 学号： 姓名： 座号： 系别： 年级： 专业： 总分合计人： 复核人： 说明：本试卷分为两部分，第I 卷（选择题和判断题）必须在“答题卡”上按规定要求填、涂；第II 卷直接在试卷上作答。不按规定答题、填涂，一律无效。 第I 卷 一、试题类型：单项选择题（每小题2分，共40分） （类型说明：在每小题列出的四个选项中只有一个选项是符合题目要求的，请选出正确选项并在“答题卡”的相应位置上涂黑。多涂、少涂、错误均无分。） 1. 算法分析的两个主要方面是： （ ） （A) 空间复杂性和时间复杂性 （B) 正确性和简明性 （C) 可读性和文档性 （D) 数据复杂性和程序复杂性 2. 计算机算法指的是： （ ） （A) 计算方法 （B) 排序方法 （C) 解决问题的有限运算序列 （D) 调度方法 3． 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称为：（ ） （A ）存储结构 （B ）逻辑结构 （C ）顺序存储结构 （D ）链式存储结构 4.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 。 （ ） （A ）110 （B ）108 （C ）100 （D ）120 5. 链接存储的存储结构所占存储空间： （ ） （A ）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 （B ）只有一部分，存放结点值 （C ） 只有一部分，存储表示结点间关系的指针 （D ） 分两部分，一部分存放结点值，另一部分存放结点所占单元数 6. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址: （ ） （A ）必须是连续的 （B ）部分地址必须是连续的 （C ）一定是不连续的 （D ）连续或不连续都可以 一、选择题 1. 算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（） A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（）。A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）(1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）】 A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）】 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A．O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 其中n为正整数，则最后一行的语句频度在最坏情况下是（） A. O（n） B. O(nlogn) C. O(n3) D. O(n2) 】 13．以下哪个数据结构不是多型数据类型（）】 A．栈B．广义表C．有向图D．字符串 14．以下数据结构中，（）是非线性数据结构】 计算机专业基础综合数据结构（概论）历年真题试卷汇编3 (总分：70.00，做题时间：90分钟) 一、单项选择题(总题数：15，分数：30.00) 1.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。【2011年全国硕士研究生入学计算机学科专业基础综合试题】简称【201 1年全国试题1(2分)】 x=2； while(x *x； （分数：2.00） A.O(log 2 n) √ B.O(n) C.O(nlog 2 n) D.O(n 2 ) 解析： 2.求整数n(n≥0)阶乘的算法如下，其时间复杂度是( )。【2012年全国试题1(2分)】int fact(int n){if(n<=i) return i；return n*fact(n一1)； （分数：2.00） A.O(log 2 n) B.O(n) √ C.O(nlog 2 n) D.O(n 2 ) 解析： 3.已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是( )。【2013年全国试题1(2)分】 （分数：2.00） A.O(n) B.O(m×n) C.O(min(m，n)) D.O(max(m，n)) √ 解析： 4.下列程序段的时间复杂度是( )。【2014年全国试题1(2分)】count=0;for(k=1；k<=n；k*=2)for(j=1；j<=n；j++)count++； （分数：2.00） A.O(log 2 n) B.O(n) C.O(nlog 2 n) √ D.O(n 2 ) 解析： 5.在数据结构中，数据的最小单位是( )。【北京理工大学2006九、1(1分)】 （分数：2.00） A.数据元素 B.字节 C.数据项√ D.结点 解析： 6.在数据结构中，数据的基本单位是( )。【北京理工大学2004五、1(1分)】 （分数：2.00） A.数据项 B.数据类型 C.数据元素√数据结构历年真题收集第1章 绪论(含答案)
数据结构试卷及答案
数据结构期末考试试题含答案
算法与数据结构试题及答案
数据结构试题及答案
数据结构期末考试试题答案详解
数据结构与算法各章试题
计算机专业基础综合数据结构(概论)历年真题试卷汇编3
相关主题
文本预览