06-09数据结构真题及答案

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个元素：

0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 38 61 84 1

如果用二次探测再散列处理冲突，关键字为49的记录的存储位置是______________。 10.具有n个顶点的无向完全图，有____________________条边。

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

1.算法在执行时，对同样的输入可以得到不同的结果。（ ） 2.线性表的链式存储结构的内存单元地址一定不连续。（ ） 3.队列允许插入的一段成为队尾，允许删除的一端称为队头。（ ） 4.拓扑排序是内部排序。（ ）

5.树转换成二叉树，其根结点的右子树一定为空。（ ）

四、综合应用题（本大题共3小题，每小题5分，共15分）

1.画出具有三个结点的二叉树的所有形态（不考虑数据信息的组合情况）。（5分） 2.写出下图的邻接矩阵，并写出其从V1出发的深度优先搜索遍历序列（5分）

V1 V4 V3 V2 V5

3.将下图所示的树转换成二叉树，并写出该二叉树的先序遍历序列。（5分） B F

C D A E G 五、算法设计（本大题共1小题，共10分）

1.已知线性表采用链式存储结构，结点类型定义如下，试编写一个算法，在带头结点的单链表L中，删除所有值为x的结点。 typedef struct LNode

2

{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.分配排序的两个基本过程是_______________________。

3

4.在拓扑排序中，拓扑序列的第一个顶点必定是_________________为0的顶点。 5.有n个结点的二叉链表中。其中空的指针域为__________________________。 6.有向图的邻接表表示适于求顶点的____________________。

7.有向图的邻接矩阵表示中，第i____________________上非零元素的个数为顶点vi的入度。 8.在树的_________________表示法中，求指定结点的双亲或祖先十分方便，但是求指定结点的孩子或其他后代可能要遍历整个数组。

9.由五个分别带权值为9,2,3,5,14的叶子结点构成一棵哈夫曼树，该树的带权路径长度为____________________。

10.具有n个顶点的有向图最多有________________条边。

三、填空题（30分）

1.写出头插法建立单链表的算法（5分）

2.求单源最短路径（从源点0开始），要求写出过程。（5分）

2 50 10 20 3 60 1 10 30 0 100 4 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，采用拉链法处理冲突，并设计出链表结构。（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]中，则入队的操作为（）

4

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.链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 （ ）

5

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.用普里姆算法构造下图的一棵最小生成树，并给出选点顺序。（以①为起点）

1 18 23 12 15 20 2 6 7 5 5 4 7 6 8 4 3 25 10

五、算法设计题（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

6

【解析】构成广义表的数据元素可以是单个元素，也可以是广义表。广义表的表头就是广义表中的第一个元素，可以是单个元素，也可以是子表。选项B、C、D都是正确的。 5. 【答案】D

【解析】在算数表达式的前缀表达式实质上就是运算符写在两个运算数的前面，当然在实现转换时，要考虑运算数的相对位置不变，而且考虑运算的优先级问题。当然，也可以采用二叉树表示出算数表达式，这样，前序遍历顺序即为前缀表达式（波兰式），后序遍历即位后缀表达式（逆波兰式），本题答案选D。 6. 【答案】D

【解析】哈夫曼树的特点是没有度为1的结点，根据二叉树的性质3，n0=n2+1，所以，具有n个叶子结点的二叉树具有n-1个度为２的结点，因此，答案选Ｄ。 7. 【答案】C

【解析】因为在中序线索二叉树中，结点X有左子树，所以，该结点前驱在左子树中，左子树中最右的结点是子树中最后一个遍历的结点，该结点可能为叶子结点，也可能是度为1的结点（即有左孩子）。 8. 【答案】A

acfbed【解析】根据本题无向图的定义，可以图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，可以确定判定树的形态如下，

631245781091112查找下标为12的元素时，先后要与下标为：6、9、11、

7

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一定是大写） ５．【答案】?log2i??1

【解析】深度为K的结点已经构成完全二叉树，所以前i个结点也为完全二叉树，所以根据性质4可以确定第i个结点的深度为?三、判断题（5分，每题1分） 1．【答案】√

【解析】链式存储结构的线性表的优点就在于实现插入和删除操作时，不需要大量元素的移动，因此，比顺序存储结构中实现插入删除操作效率高。 2．【答案】×

【解析】实现二叉树的按层遍历时，应借助于一个队列作为辅助结构。 3．【答案】√

【解析】树转换为二叉树是依据的孩子兄弟表示法这种存储结构，树根没有兄弟，所以，一棵树转换成二叉树，对应二叉树根结点没有左子树。 4．【答案】×

【解析】有向图的邻接表中结点的个数与逆邻接表中结点的个数是相等的，都等于图中所有顶点的入度和（或出度和）的值。 5．【答案】×

【解析】就平均时间而言，快速排序目前被认为是最好的一种内部排序方法，但是，当待排序列基本有序时，快速排序将蜕化为冒泡排序，因此，排序效果反而降低。 四、综合应用题（本大题共3小题，每小题5分，共15分） 1．答：根据结点画出二叉排序的过程如图所示：

log2i??1 。

8

464688454688394546883945468870394546887058464539587088101103958454688701011039584546468845701013910663466587010188

等概率情况下，平均查找长度为：（5*2+4*2+3*3+2*2+1*1）/10=3.2

2．答：根据哈希函数和处理冲突的方法为二次探测再散列，构造哈希表如图所示：

014112932348452765572089

【解析】注意关键字的顺序,9%7=2; 1%7=1; 23%7=2,冲突,但是(2+12)=3;14%7=0; 55%7=6;20%7=6,冲突,但是(6+12)=7;84%7=0,冲突,但是(0+12)=1,已经占用,由于函数值已经是0了，在这里不能再试探-12,因此(0+22)=4,所以84存储在下标4的单元格内。最后27%7=6，冲突，(6+12)=7，仍然冲突，（6-12)=5，所以27存储在下标5的单元格内。

3．答：根据每个字符出现的频率，我们可以求解哈夫曼树，为方便求解，不妨将频率变为整数，则权值分别为：7，19，2，6，32，3，21，10，由此构造哈夫曼如图：

0600280110502131607117110132019100140121

由此可以设定每个字符的哈夫曼编码：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.答:根据普里姆算法构造最小生成树,如下图所示:

9

14676146761418267141825376146188253618456412861246753

五、算法设计（本大题共１小题，共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

【解析】线性表的顺序存储结构要求分配连续的存储空间，因此，可以实现数据元素的顺

10

序存取以及随机存取。但元素的插入和删除需要涉及大量元素的移动；而线性表的链式存储方便于元素的插入与删除，但是不能实现随机存取，只能进行顺序存取。 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.【答案】出度

【解析】有向图的邻接表是指:所有顶点建立顶点结点，以每个顶点为弧尾的所有弧对应的另外一个顶点序号构成表结点链接形成的单链表。所以，通过计数每个单链表中表结点的

11

个数，可以计算每个顶点的出度。 7．【答案】列

【解析】有向图的邻接矩阵的特点是，通过求解每一行上1的个数，可以求解每个顶点的出度；通过求解每一列上1的个数，可以求解每个顶点的出度。无向图的邻接矩阵属于对称矩阵，每个顶点的度即为行或列上1的个个数。 8.【答案】双亲

【解析】树的表示方法一共有三种，双亲表示法、孩子表示法以及孩子兄弟表示法。其中双亲表示法为每个树中元素建立一个结点，包括存储数据元素本身，以及该结点的双亲结点的存储下标，所以，该存储方法可以很容易的求解结点的双亲以及祖先，但是求解结点的孩子及后代需要遍历整个数组。 9．【答案】67。

3319141095235【解析】。图为五个权值形成的哈夫曼树，树的带权路径长度为：

(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．答：

12

1 求顶点0其余各顶点的最短路径 10 (0,1) / / / 2 ∞ 60 (0,1,2) 50 (0,3,2) / / 3 30 (0,3) 30 (0,3) 100 (0,4) 3 / 4 100 (0,4) 90 60 (0,3,4) (0,3,2,4) 2 添加 顶点 1

3．答：根据（1）中序遍历的特点：左子树、根、右子树的遍历顺序；（2）后序遍历的特点：左子树、右子树、根；（3）二叉树的每棵子树也符合该特性。所以，该二叉树的构造过程为:

aabdfbechiddfehifheiabcc

由此可得到二叉树的前序遍历顺序为：abdfceih 4．答：根据二叉排序树的定义，创建过程如下图：

1515443043041130411515154115154112230441111224130

5. 答：

该邻接表的结构描述如下： #define VERTEX_MAX 100 typedef struct node {int adjvex; struct node *next;

}Edgenode; //表结点的类型定义

13

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;vn;v++) visited[v]=FALSE; InitQueue(Q)； for(v=0;vn;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．答：根据哈希函数以及拉链法解决冲突，构造如下哈希表：

14

01234567891011122311192014012779∧ 6855∧ 84∧ 10∧ ∧

山东省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

15

【解析】在二叉链表中每个结点有两个指针域，而除了根结点外，每个结点均需要占用其中一个指针域，所以空的指针域个数为：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. 【答案】2 -1

【解析】二叉树的基本性质２。 5．【答案】e

【解析】有向图的邻接表是以图中所有顶点作为头结点，将所有以该顶点为弧尾的弧生成表结点构成的。所以，表结点数与弧数是一一对应的。 6.【答案】中序

【解析】二叉排序树中所有左子树中结点均比根结点的值小，所以右子树中结点值均比根结点的值大，如果左右子树不空，左右子树都满足该特性，所以二叉排序树的中序遍历顺序是由小到大的顺序排列的。 7．【答案】2

【解析】无论在有向图还是在无向图中，每条边或弧在计算顶点的度时均被用过２次，所以，得到的顶点的度的和就是边数的２倍。 8.【答案】3

【解析】该有序表中包含７个元素，因此先与第４个元素进行比较，然后和第２个元素进行比较，最后和第３个元素进行比较，所以共需要比较３次成功。

K

16

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种基本形态，具体如下图所示：

２

２

２

２

?0?1?2．答： ?1??1??0V2

1110?0001??0000?如图为该图的邻接矩阵。从V1出发的深度优先遍历顺序为

?0001?1010??V1→V4→V5→V2→V3或V1→V2→V5→V4→V3或V1→V3→V2→V5→V4或V1→V3→V4→V5→

17

3．答：树转换为二叉树为：其中该二叉树的先序遍历顺序为A，B，C，E，F，G，D

ABCEFDG

五、算法设计（本大题共１小题，共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向后移动。 } } }

18

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.字符串

19

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=\，则指针s所指字符串的长度为（A.19 B.15 C.18 D.说明不合法 14.下述对C语言字符数组的描述中错误的是（ ） A.字符数组可以存放字符串

B.字符数组中的字符串可以整体输入、输出

C.可以在赋值语句中通过赋值运算符对字符数组整体赋值 D.不可以用关系运算符对字符数组中的字符串进行比较 15.设有如下的函数 exam(float x){ printf(\

}

则函数的类型为（ ）

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(\

} } 答案： 2、程序： main() { int k=3,n=0;

20

）

while(k>0) {switch(k)

{case 1: n+=k; case 2: case 3: n+=k;

default: break; } k--;

}

printf(\} 答案： 3、程序： main()

{ int i,j,row,column,m;

static int array[3][3]={{100,200,300},{28,72,-30},{-850,2,6}}; m=array[0][0]; for(i=0;i<3;i++) for(j=0;j<3;j++) if(array[i][j]

}

printf(\} 答案： 4、程序

#include int p(int k,int a[]) { int m,i,c=0;

for(m=2;m<=k;m++) for(i=2;i

{if(!(m%i)) break;

if(i= =m) a[c++]=m;

} return c; }

#define MAXN 20

21

main() {

int i,m,s[MAXN]; m=p(13,s); for(i=0;i

return f(n-2)+2*f(n-1); } main() { int n=5; printf(\} 答案：

八、程序填空：按要求完成下面的程序（函数）（每空2分，共10分）

1.本函数用对分查找法，在以按字母次序从小到大排序的字符数组list中查找字符c，若c在数组中，函数返回字符c在数组中的下标，否则返回-1。 int search（char list[],char c,int len） { int low.hige,k;

low=0; high=len-1; while(__⑴__) {k=(low+high)/2; if(__⑵__) return k; else if(__⑶__) high=k-1; else low=k+1; } return -1; }

答案：（1） （2） (3)

2.函数mycmp(char *s，char *t)的功能是比较字符串s和t的大小，当s等于t时返回0，否则返回s和t的第一个不同字符的ASCII码的差值。

22

mycmp(char *s，char *t) { while(*s= =*t) { if(__⑷__)return 0; ++s; ++t;

}

return (___⑸__); }

答案：（4） （5）

07C语言（50分）

四、填空题（本题20分，每空2分）

1.C语言中规定，整型常量可以用十进制、二进制和___________进制形式来表示。 2.结构化程序设计中的三种基本结构为顺序结构、______________和循环结构。 3.在C语言中，对于负整数，在内存中是以_____________码形式进行存储。

4.在C语言中，若被定义为int类型的变量，在内存中占用__________个字节的存储空间。 5.已有定义：int a[5]，*p；当执行了p=&a[3]；语句时，是将指针变量p指向了a数组的第______________个元素的地址。

6.若某变量被定义为auto变量的存储单元，则将被分配在内存的_____________存储区域。 7.在下列给出的字符数组c，它在内存中所占用的字节数是_____________。

char c[]={\

8.在C语言中，能够实现循环结构的语句有：while语句、if/goto语句、do-while语句以及__________________语句。

9.若有a=3，b=5；则求a>b的关系运算结果是___________________________。 10.若定义int a[10];则允许数组a的下标值最小可以是__________________________。

五、请写出下列程序的运行结果（本题10分，每小题2分）

1.main() { int n=100; if(n>100) printf{\else printf(\} 2.main()

{ int a=2,b=-1,c=2; if(a

23

printf(\} 3.main()

{ char s[]=\printf(\} 4.main() { int a=3,b=4;

printf(\} 5.main()

{ static int a[5],i;

for(i=0;i<5;i++)a[i]=a[i]+i; for(i=0;i<5;i++)printf(\}

六、单选题（本题10分，每小题2分）

1.main() { int k=11;

printf(\}

A.k=11,k=12,k=11 B.k=11,k=13,k=13 C.k=11,k=013,k=0xb D.k=11,k=13,k=b 2.main() { int y=10; while(y--);

printf(\}

A.y=10; B.y=1 C.y=随机值 D.y=-1 3.main()

{ int a,b,*p1,*p2; p1=&a;p2=&b;

*p1=100;*p2=200;c=*p1+*p2; printf(\}

A.300 B.100+200 C.100 D.200

4.在下列程序中，当执行到gets(ss)；语句时，若输入字符为“ABC”时，则该程序的输出结果是： main()

{ char ss[10]=\

24

stract(ss,\ gets(ss);printf(\}

A.ABC B.ABC9 C.123456ABC D.ABC456789 5.main()

{ char a[]=\ int i,j=0; for(i=1;i<7;i++) if(a[j]

A.mogninr B.mo C.morning D.mornin

七、编程题（10分，每题5分）

1.请将下列一组数据读入到S数组中，并从中找出最小的值并输出。

30，56，88，45，100，20

2.请将下列给出的字符串读入到ss数组中，并输出该字符串。

Student and Teacher

25

本文来源：https://www.bwwdw.com/article/riyp.html