数据结构题目求答案1、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中,用折半查找法查找关键字值20,需做的关键字比较次数为.2、抽象数据类型的三大要素为、和.3、

Question

数据结构题目求答案
1 、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中,用折半查找法查找关键字值20,需做的关键字比较次数为 .
2、抽象数据类型的三大要素为 、 和 .
3、空格串的长度等于 .
4 、栈和队列的区别仅在于 操作定义不相同.
5、设一个线性表的长度为50,P是指向线性链表的第10个元素,且P->next->next 指向第 元素.
6、二叉树的第i层最多有 个结点,深度为k的二叉树最多有 个结点.
7、利用MST性质来构造最小生成树的两种常用算法为_________和__________.
8、常见的四类基本数据结构有：________、_________、__________、___________.
二、判断(对的打∨,错误打×, 10×2 = 20 分)
1、由于链式存储结构不要求逻辑上相邻的元素在物理位置上也相邻,因此,它具有随机存取的优点( ).
2、赫夫曼树是指带权路径长度WPL最小的二叉树.一般而言,在给定条件下构造出的赫夫曼树不是唯一的 ( ).
3、非空完全二叉树的一个任意结点的右子树深度与其左子树深度的差值或者为0或者为1( ).
4、先序遍历二叉排序树可得到一个关键字有序的序列( ) .
5、在n个结点的无向图,若边数大于n-1,则该图必是连通图 ( ).
6、在n个元素进栈后,它们的出栈顺序和进栈顺序一定正好相反( ).
7、往顺序表中插人一个元素,平均要移动大约一半的元素( ).
8、类似于算法的时间复杂度,空间复杂度可以作为算法所需存储空间的量度( ).
9、赫夫曼树一定是满二叉树( ).
10、队列的基本特征是先进后出( ).
三、选择题（10×2=20分）
1、有六个元素6,5,4,3,2,1 的顺序进栈,问下列哪一个不是合法的出栈序列?( )
A. 2 3 4 1 5 6 B. 1 2 4 5 3 6
C. 6 4 5 1 2 3 D. 4 5 3 1 2 6
2、一棵完全二叉树上有1001个结点,其中叶子结点的个数是
A. 254 B. 500
C. 250 D. 以上答案都不对
3、线性链表不具有的特点( ).
A.随机访问 B.不必事先估计所需存储空间大小
C.插入与删除时不必移动元素 D.所需空间与线性表长度成正比
4、向顺序栈中压入新元素时,应当( ).
A.先移动栈顶指针,再存入元素 B.先存入元素,再移动栈顶指针
C.先后次序无关紧要 D.同时进行
5、具有65个结点的完全二叉树的高度为( ). (根的层次号为1)
A.8 B.7
C.6 D.5
6、由权值分别为3,8,10,2,6的叶子结点生成一棵哈夫曼树,则其中非终端结点数为( ).
A. 2 B. 3
C. 4 D. 5
7、n个顶点的有向完全图中含有向边的数目最多为( )
A.n-1 B.n C.n(n-1)/2 D.n(n-1)
8、一个对象序列的排序码为{46,79,56,38,40,84},采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为( ).
A.{38,46,79,56,40,84} B.{38,79,56,46,40,84}
C.{40,38,46,56,79,84} D.{38,46,56,79,40,84}
9、长度为11的哈希表中已经填有关键字17,60,29的记录,采用二次探测再散列方法解决冲突,则填入关键字38其地址应该为( )（哈希函数为h(key)=key mod 11）
A.4 B.5
C.3 D.6
10、在一个无向图中,所有顶点的度数之和等于所有边数的( )倍.
A.3 B.2
C.1 D.1/2
我汗啊!都回答错了,

Answer 1

3.28
void InitCiQueue(CiQueue&Q)//初始化循环链表表示的队列Q
{
Q=(CiLNode*)malloc(sizeof(CiLNode));
Q->next=Q;
}//InitCiQueue
voidEnCiQueue(CiQueue&Q,int x)//把元素x插入循环列表表示的队列Q,Q指向队尾元素,Q->next指向头结点,Q->next->next指向队尾元素
{
p=(CiLNode*)malloc(sizeof(CiLNode));
p->data=x;
p->next=Q->next;//直接把p加在Q的后面
Q->next=p;
Q=p;//修改尾指针
}
Status DeCiQueue(CiQueue&Q,int x)//从循环链表表示的队列Q头部删除元素x
{
if(Q==Q->next)return INFEASIBLE;//队列已空
p=Q->next->next;
x=p->data;
Q->next->next=p->next;
free(p);
rturn OK;
}//DeCiqueue
3.31
int Palindrome_Test()
{
InitStack(S);InitQueue(Q);
while((c=getchar())!='@')
{
Push(S,c);EnQueue(Q,c);
}
while(!StackEmpty(S))
{
pop(S,a);DeQueue(Q,b);
if(a!=b)return ERROR;
}
return OK;
}