数据结构题目求答案

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

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

Answer 2

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

Answer 3

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;
}
本回答被网友采纳

Answer 4

太废脑筋了，懒得想。高手来吧。

Answer 5

第一题26、15、19、25