同的结点,每个结点有两个域 域和 域。其中 域用于用于存放数据， 域用于存放下一个结点的指针 三．判断

1. 顺序存储的线性表可以随机存取。 （ ） 2. 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同。 （ ）

3. 十字链表是无向图的一种存储结构。（ ）

4. 折半查找方法适用于排列连续顺序文件的查找。（ ）

5. 在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（ ） 四、应用题

1. 用十字链表表示一个有k个非零元素的m x n的稀疏矩阵，则其总的结点数为多少？

2. G=(V,E)是一个带有权的连通图,则： （1）．请回答什么是G的最小生成树；

（2）．G为下图所示,请找出G的所有最小生成树。

3. 请分别叙述在一个连续顺序文件中采用顺序查找法，折半查找法和分块查找法查找一个记录，该文件中记录应该满足什么条件？

4. 设待排序文件之排序码为（88，33，22，55，99，11，66），采用顺序存储。请用直接选择排序算法对上述文件进行排序，用图示说明排序过程。

东北农业大学网络教育学院 数据结构专升本作业题参考答案

作业题一参考答案：

一、单项选择题

1、C 2、B 3、D 4、C 5、B 6、B 7、A 8、C 9、D 10、D 二、填空题 1、非零元很少

2、操作受限（或限定仅在表尾进行插入和限定仅在表头进行删除操作或限制存取点或特殊），先进先出(或后进后出)

3、简单选择排序 4、O(n2)，O(e)，O(n) 5、邻阵矩阵，邻接表 三、算法 答： int count = 0;

void onechild ( Btree t) { if ( t!=NULL) { onechild ( t->lchild ); onechild ( t->rchild );

if ( t->lchild!=NULL && (t->rchild!=NULL || t->lchild!=NULL && t->rchild==NULL )

count++;

} }

四、应用题 1、 答：

2、 答：

（1） （2） C 1 C 1

G G 2 F

（3） A 3 （4）D A 3 D C 1 G 2 F