《数据结构C》模拟试题
图9.2
8.下列算法实现二叉搜索树上的查找,请在空格处填入适当的语句,完成上述功能
public Node<T> Search(Node<T> root, T value)
{
Node<T> p = root;
if (p == null)
{
return null;
}
if (!p.Data.Equals(value))
}
}
Qc.Next=Hc;
}
return Hc;
}
3.解答
public int Judge(LinkList<T> Head)
{
bool flag=false;
int i=2;
LinkList<T> P;
LinkList<T> Q;
Q=Head.Next;
while(P!=null)
{
if(P.Data==i*i-Q.Data)
{
flag=true;
}
else
{
return false;
}
Q=P;
P=P.Next;
++i;
}
return flag;
}
《数据结构C》模拟试题二
班级姓名学号
一、选择题(20分)
1.数据结构是研究数据的( )以及它们之间的相互关系。
(A)理想结构、物理结构(B)理想结构、抽象结构
(C)物理结构、逻辑结构(D)抽象结构、逻辑结构
,判满的条件是。
2.循环链表的主要优点是。
3.给定一个整数集合{3,5,6,9,12},画出其对应的一棵Huffman树。
4双向循环链表中,在p所指的结点之后插入f所指的结点,其操作为。
5.下列为朴素的模式匹配算法,请在算法的处填入正确的子句。
public int insert(string s, string t)
Push,Push,Pop,Push,Pop,Push,Push后,输出序列为。
4.线索化二叉树中某结点D,没有主孩子的主要条件是。
5.“ababbabbab”的前缀函数为。
6.设图G的顶点数为n,边数为e,第i个顶点的度数为D(vi),则e=(即边数与各顶点的度数这间的关系)。
7.按遍历二叉树,可以得到按值递增的关键码序列。已知二叉树如图9.2所示,在检索关键字85的过程中,需与85进行比较的关键字系列为。
(A) ‘BCQR’ (B) ‘BCDEF’ (C) ’BCDEFG’ (D) ‘BCDEFEF’
8.有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一元素,其存储地址为1,每个元素占1个地址空间,则a85地址为( )
(A)13 (B) 33 (C) 18 (D) 40
9.如果结点A有3个兄弟,而且B为A的双亲,则B的度为( )
(A) 3 (B) 4 (C) 5 (D) 1
10.线索化二叉树中某结点D没有左孩子的必要条件是( )
(A) D.Lchild=null (B) D.ltag=1
(C) D.Rchild=null (D) D.ltag=0
二、填空题(20分)
1.对于一个以顺序实现的循环队列Q[0..m_1],队头、队尾指针分别为f,r,其判空的条件是
5. i-j-1,0
6. n(n+1)/2
7. n+1
8.单右支二叉树或孤立结点
9.
三、应用题
1.答:
(1)该存储结构对应的二叉树为:
(2)前序序列为E A D C B F H G I
中序序列为A B C D E F G H I
后序序列为B C D A G I H F E
(3)后序线索树为:
2.存在,12的双亲结点为6
{
int i = 0;
int j = 0;
while (i < s.Length && j < t.Length)
{
if (s[i] == t[j])
{
i = i + 1;
j = j + 1;
}
else
{
i =
j =
}
}
if (j == t.Length)
{
return i - t.Length;
}
三、应用题(18分)
1.设二叉树的顺序存储结构如下。(6分)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
E
A
F
^
D
^
H
^
^
C
^
^
^
G
I
^
^
^
^
B
(1)根据其存储结构画出三叉树;
(2)写出按前序、中序、后序遍历该二叉树所得的结点序列。
(3)画出二叉树的后序线索树。
6.设一数列的输入顺序为1,2,3,4,5,6,通过栈操作不可能排成的输出序列为( )
(A) 3,2,5,6,4,1 (B) 1,5,4,6,2,3
(C) 2,4,3,5,1,6 (D) 4,5,3,6,2,1
7.设字符串S1=’ABCDEFG’,S2=’PQRST’,则运算S=CONCAT(SUB(S1,2,LENGTH(S2)),SUB(S1,LENGTH(S2),2))的结果为( )
num2 = nodes(root.RChild);
}
return num1 + num2 + 1;
}
2.解答:算法描述如下
public LinkList<T> Merge(LinkList<T> Ha, LinkList<T> Hb)
{
LinkList<T> Hc;
LinkList<T> Qa;
LinkList<T> Qb;
(A)线性表(B)栈(C)队列(D)树
4.二叉树第i(i≥1)层最多有( )个结点。
(A) 2i(B)2i (C) 2i-1(D) 2i-1
5.设单链表中p指向结点A,若要删除A后结点(若存在),则需要修改p的操作为( )
(A) p.Next = p.Next.Next (B)p=p.Next
(C)p=p.Next.Next (D)p.Next=p
山东科技大学继续教育学院
《数据结构C》模拟试题一
班级姓名学号
题号
一
二
三
四
五
六
总得分
评卷人
审核人
得分
一、选择题(20分)
1.组成数据的基本单位是( )。
(A)数据项(B)数据类型(C)数据元素(D)数据变量
2.线性表的链接实现有利于( )运算。
(A)插入(B)读表元(C)查找(D)定位
3.串的逻辑结构与( )的逻辑结构不同。
else
{
return -1;
}
}
6.一个n*n的对称矩阵,如果以行或列为主序存入内存,则其容量为。
7.设F是森林,B是由F转换得到的二叉树,F中有n个非终端结点,B中右指针域为空的结点有。
8.前序序列和中序序列相同的二叉树为。
9.已知一棵二叉树的中序遍历结果为DBHEAFICG,后序遍历结果为DHEBIFGCA,画出该二叉树。
LinkList<T> Qc;
if(Ha==null)
{
Hc=Hb;
}
if(Hb==null)
{
Hc=Ha;
}
if(Ha!=null&&Hb!=null)
{
Qa=Ha;
Qb=Hb;ຫໍສະໝຸດ Hc=Ha;Qa=Qa.Next;
Hc.Next=Qb;
while(Ha!=Qa&&Hb!=Qb)
{
Qc.Next=Qa;
10.在内部排序中,排序时不稳定的有( )。
(A)插入排序(B)冒泡排序(C)快速排序(D)归并排序
二、填空题(22分)
1.具有64个结点的完全二叉树的深度为。
2.有向图G用邻接矩阵A{1…n,1…n}存储,其第i列的所有元素等于顶点i的。
3.设有一空栈,栈顶指针为1000H(十六进制),现有输入序列为1,2,3,4,5,经过
《数据结构C》模拟试题一 参考答案
一、选择题
题号
1
2
3
4
5
6
7
8
9
10
答案
C
A
D
C
A
B
D
B
D
B
二、填空题
1. r =f ,(r+1)% m = f
2.从任一结点出发可以遍历链表中的所有结点
3.
4.
(1)f.Next = p.Next;
(2)p.Next.Prev=f;
(3)f.Prev = p;
(4)p.Next = f;
4.完成堆排序的全过程需要( )个记录大小的辅助空间。
(A) 1 (B) n (C) nlog2n (D) n2
5.若给定关键字集合为{20,15,14,18,21,36,40,10},一趟快速排序结束时,键值的排列为( )
(A) 10,15,14,18,20,36,40,21 (B) 10,15,14,18,20,40,36,21
f(t)=f(root.LChild) +f(root.RChild)+1其他
因此,实现本题功能的方法为:
public int nodes(Node<T> root)
{