《算法与数据结构》模拟试题3
一、填空题（每小题2分，共18分）
1、 数据的逻辑结构包括 ， 和 三种结构。
2、 算法分析的两个主要方面是 和 。
3、 在双向链表中，每个结点有两个指针域，一个指向 ，
另一个指向 。
4、 空串是 ，其长度等于 。
5、 有一个10阶对称矩阵A，采用压缩存储方式，以行为主存储下三角形到一个一维数组中，若A[0][0]的地址是200（每个元素占2个基本存储单元），则A[9][5]的地址是 。
6、 在非空二叉树的中序遍历序列中，根结点的右边 。
7、 采用邻接链表存储图，则图的深度优先搜索算法类似于二叉树的 。
8、 在分块查方法中，首先查 ，然后再查相应的 。
9、 对于文件，按其记录的类型可将文件分为 文件、 文件。
二、单项选择题（请将答案写在题目后的括号中。每题2分，共数据结构与算法分析答案18分）
1、有如下递归函数fact(n)，其时间复杂度是（ ）。
Fact(int n)
{ if (n<=1) return 1;
else return(n*fact(n-1)) ;
}
（A） O(n) （B） O(n2) （C） O(㏒2n) （D） O(n㏒2n)
2、 设有一个栈顶指针为top的顺序栈S，top为0时表示栈空，则向S中压入一个元素P执行的操作是（ ）。
（A） S[top++]=p； （B） S[++top]=p；
(C) S[--top]=p； （D） S[top--]=p；
3、 稀疏矩阵一般的压缩存储方法有主要有（ ）两种。
（A） 二维数组和三维数组 （B） 三元组和散列
（C） 三元组和十字链表 （D） 散列和十字链表
4、 一般树的存储结构主要有（ ）。
（A） 双亲表示法，孩子表示法，链表表示法
（B） 双亲表示法，孩子表示法，孩子—兄弟表示法
（C） 双亲表示法，孩子—兄弟表示法，链表表示法
（D） 双亲表示法，孩子—兄弟表示法，链表表示法
5、 一棵有n(n≥0)个结点的满二叉树的叶子结点的数目是 ，非叶子结点的数目是 。（ ）
（A） 2[㏒2n] 2[㏒2n] （B） 2[㏒2n]-1 2[㏒2n]
（C） 2[㏒2n]-1 2[㏒2n]-1 （D） 2[㏒2n] 2[㏒2n]-1
6、 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍，
所有顶点的度之和等于所有顶点的入度之和的 倍。（ ）
（A） 1/2，1 （B） 1，2 （C） 2，1 （D） 1，4
7、设有一个长度为12的有序表，采用二分查方法对该表进行查时，在表内各元素等概率情况下查成功所需的平均比较次数为。（ ）
(A) 35/12 （B） 37/12 （C） 39/12 （D） 43/12
8、 设有一组记录的关键字是（37，28，56，80，60，14，25，50），用快速排序法以第一个记录为基准得到的一次划分结果是（ ）。
（A） 25，28，37，14，56，80，60，50 （B） 25，28，37，14，60，80，56，50
（C） 25，28，14，37，60，80，56，50 （D） 25，28，14，37，60，56，80，50
9、 文件在外存上的上的组织方式称为文件的物理结构。基本的物理结构有：（ ）
(A) 顺序结构，链接结构，线性结构 (B) 线性结构，链接结构，索引结构
(C) 顺序结构，链接结构，线性结构 (D) 顺序结构，链接结构，索引结构
三、分析题（每题6分，共30分）
1、 设有一棵二叉树，其先序遍历序列是abdgehicf，中序遍历序列是gdbheiafc，请画出这棵二叉树，然后画出其后序线索化树。
2、 对于下图中的网，写出该网的邻接链表；然后写出其广度优先搜索生成树（假设从顶点V1出发）；最后给出按Prime算法从顶点V5出发得到的最小生成树。
3、 将关键字序列（14，9，18，7，4，13，25，19，6）依此插入到初态为空的二叉排序树中，请画出所得到的树T；然后画出删除18之后的二叉排序树T1；最后再画出插入18之后的二叉排序树T2。
4、 线性表的关键字集合{71，25，8，29，42，69，95，33，17，56，47}，共有11个元素，已知散列函数为：H（k） = k MOD 11，采用链地址处理冲突，请给出对应的散列表结构，并计算该表成功查的平均查长度。
5、 已知序列{35，29，52，60，17，9，38，27，13，45}，请给出采用归并排序法对该序列做非递减排序时的每一趟结果。
四、算法填空（每空2分，共20分）
请在下面各个算法的空白处填上相应的语句，以实现算法功能。每个空白处只能填一个语句。
1、 循环队列Q的队首元素出队操作算法。
#define Max_Queue_Size 100
ElemType Delete_CirQueue(SqQueue Q)
{ ElemType x ;
if ( )
printf(“The Circular Queue is Null!”) ;
else { x=Q.Queue_array[Q.front] ;
;
}
}
2、 二叉树中序遍历的非递归算法。
#define Max_Node_Num 50
Void InorderTraverse( BTNode *T)
{ BTNode *Stack[Max_Node_Num] ,*p=T ;
int top=0 , bool=1 ;
if (T==NULL) printf(“The Binary Tree is Empty!\n”) ;
else { do { while (p!=NULL)
{ stack[++top]=p ; p=p->Lchild ; }
if (top==0) bool=0 ;
else { ;
visit( p->data ) ; ; }
} while ( ) ;
}
}
3、 折半查算法。
int Bin_Search(SSTable ST , KeyType key)
{ int Low=1，High=ST.length, Mid ;
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论