发布时间 : 星期二 文章自考数据结构02331历年试题及答案（2009--2015个人整理版） - 图文更新完毕开始阅读f39217d870fe910ef12d2af90242a8956aecaa04
33．下面程序实现二分查找算法。 Typedef struct{
KeyType key；
InfoType otherinfo； }SeqList[N+1]；
int BinSearch(SeqList R, int n，KeyType K) { int low=1，high=n；
while( (1) low<=high ){
mid=(1ow+high)／2；
if( (2) R[mid].key==K )
return mid； if(R[mid]．key>K)
high=mid-1； else
(3) low=mid+1 ；
}
return O； } ／／BinSearch
请在空白处填写适当内容，使该程序功能完整。 (1) (2) (3)
五、算法设计题(本题10分)
34．已知二叉树采用二叉链表存储，其结点结构定义如下： typedef struct Node{
ElmType data；
struct Node *lchild，*rchild； }*BiTree；
请编写递归函数SumNodes(BiTree T)，返回二叉树T的结点总数。 求二叉数的结点总数满足如下的递归定义：
①若T为空，则以T为根的二叉树中结点总数为0；
②否则，以T为根的二叉树中结点总数应该是根T的左子树和右子树中结点数之和再加上根本身。 int SumNodes(BiTree T){ //T的初值指向某二叉链表的根结点 if(! T) //T为空 return 0; else
return SumNodes(T->lchild)+ SumNodes(T->rchild)+1; }
全国2010年10月自学考试数据结构试题
一、单项选择题（本大题共15小题，每小题2分，共30分） 1.数据的四种存储结构是( )
A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构 B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构 C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构
D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构
2.若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中，应选择的存储结构是( ) A.无头结点的单向链表 C.带头结点的双循环链表
B.带头结点的单向链表 D.带头结点的单循环链表
3.若带头结点的单链表的头指针为head，则判断链表是否为空的条件是( ) A.head=NULL C.head!=NULL
B.head->next=NULL D.head->next!=head
4.若元素的入栈顺序为1，2，3....，n，如果第2个出栈的元素是n，则输出的第i(1<=i<=n)个元素是( ) A.n-i C.n-i+2
5.串匹配算法的本质是( ) A.串复制 C.子串定位
B.串比较 D.子串链接 B.n-i+l D.无法确定
6.设有一个10阶的对称矩阵A，采用行优先压缩存储方式，a11为第一个元素，其存储地址为1，每个元素占一个字节空间，则a85的地址为( ) A.13 C.33
7.若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是( ) A.树中没有度为2的结点 C.树中非叶结点均只有左子树
B.树中只有一个根结点 D.树中非叶结点均只有右子树 B.18 D.40
8.若根结点的层数为1，则具有n个结点的二叉树的最大高度是( ) A.n
C. +1
B. D.n/2
9.在图G中求两个结点之间的最短路径可以采用的算法是( ) A.迪杰斯特拉（Dijkstra）算法 C.普里姆(Prim)算法
B.克鲁斯卡尔（Kruskal）算法 D.广度优先遍历(BFS)算法
10.下图G=(V,E)是一个带权连通图，G的最小生成树的权为( ) A.15 B.16 C.17 D.18
11.在下图中，从顶点1出发进行深度优先遍历可得到的序列是( ) A.1 2 3 4 5 6 7 B.1 4 2 6 3 7 5 C.1 4 2 5 3 6 7
D.1 2 4 6 5 3 7
12.如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是( ) A.不稳定的 C.基于交换的
B.稳定的 D.基于选择的
13.设有一组关键字(19, 14, 23, 1，6，20, 4，27, 5，11, 10, 9)，用散列函数H(key)=key构造散列表，用拉链法解决冲突，散列地址为1的链中记录个数为( ) A.1 C.3
B.2 D.4
14.已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是( D )
15.若需高效地查询多关键字文件，可以采用的文件组织方式为( ) A.顺序文件 C.散列文件
B.索引文件 D.倒排文件
二、填空题（本大题共10小题，每小题2分，共20分）
请每小题的空格中填上正确答案。错填、不填均无分。 16.下面程序段的时间复杂度为______O（n）_____。
sum=1；
for（i=0；sum sum+=1； 17.已知链表结点定义如下： typedef struct node{ char data［16］； struct node *next; } LinkStrNode； 如果每个字符占1个字节，指针占4个字节，则该链表的存储密度是_ 4/5_______。 18.使用一个100个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队空和队满，约定队头指针front等于队尾指针rear时表示队空。若为front=8，rear=7，则队列中的元素个数为_____99______。 19.3个结点可以组成_____5______种不同树型的二叉树。 20.用5个权值{3, 2，4，5，1}构造的哈夫曼(Huffman)树的带权路径长度是______33_____。 21.若无向图G中有n个顶点m条边，采用邻接矩阵存储，则该矩阵中非0元素的个数为____2m_______。 22.影响排序效率的两个因素是关键字的______比较_____次数和记录的移动次数。 23.对任一m阶的B树，每个结点中最多包含____m-1_______个关键字。 24.若两个关键字通过散列函数映射到同一个散列地址，这种现象称为____冲突_______。 25.如果要为文件中的每个记录建立一个索引项，则这样建立的索引表称为____稠密索引_______。 三、解答题（本大题共4小题，每小题5分，共20分） 26.要在［0..n-l］的向量空间中建立两个栈stackl和stack2，请回答： (1)应该如何设计这两个栈才能充分利用整个向量空间？ (2)若stackl的栈顶指针为topl,stack2的栈顶指针为top2，如果需要充分利用整个向量空间，则： 栈stackl空的条件是：___________； 栈stack2空的条件是：___________； 栈stackl和栈stack2满的条件是：___________。 27.已知广义表如下： A=(B,y) B=(x，L) L=(a，b) 要求： (1)写出下列操作的结果 tail(A)=_______________. head(B)=______________。 (2)请画出广义表A对应的图形表示。 28.已知二叉树如下： 请画出该二叉树对应的森林。 29.请回答下列问题： (1)英文缩写DAG的中文含义是什么？ (2)请给出下面DAG图的全部拓扑排序。 四、算法阅读题（本大题共4小题，每小题5分，共20分）