📄 数据结构热身题之填空题 - 考研论坛.htm
字号:
在带头结点的双循环链表L中，最后一个结点的指针是 。<BR>0. 在双循环链表L中，指针P所指结点为尾结点的条件是 。<BR>1.
在双循环链表L中，删除指针P所指结点的语句序列是 。<BR>1.
在双链表中，在指针P所指结点前面插入一个结点S↑的语句序列是：<BR>S↑.next:=P;S↑.prior:=P↑.prior;P↑.prior:=S;
。<BR>2. 已知栈的输入序列为1,2,3,…,n.，输出序列为a1,a2,…, an, a2=n的输出序列共有
种。<BR>3．设S[1..maxsize]为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件是 ，栈为满的条件是 。<BR>4.
若一个栈的输入序列为1~n，则其输出序列的第二个元素为n的输出序列的个数是 。<BR>5.
设sq[1..maxsize]为一个顺序存储的栈，变量top指示栈元素的位置。能作入栈操作的条件是
。如要把栈顶元素弹出并送到x中，则需要执行下列语句： 。<BR>6.
循环队列采用数组data[1..n]来存贮元素的值，并用front和rear分别作为其头尾指针。为区别队列的满与空，约定队中能够存放的元素最大为n-1，即至少有一个元素空间不用，则在任意时刻，至少可以知道一个空的元素的下标是
。入队时，可用语句 求出新元素在数组data中的下标。<BR>7. 队列的特征是 。<BR>8.
已知循环队列用数组data[1..n]存储元素值，用f,r分别作为头尾指针，则当前元素个数为 。<BR>9.
对广义表A=(x,((a,b),c,d))的运算head(head(tail(A)))的结果是 。<BR>0.
取出广义表A=((a,x,y,z),(b,c))中原子c的复合函数是 。<BR>1.
取出广义表A=((x,y,z),(a,b,c,d))中原子b的函数是 。<BR>S↑.next:=P; S↑.prior:=P↑.prior;
P↑.prior:= S; :=S;<BR>2. 取出广义表A=(x,(a,b,c,d))中原子b的函数是 。<BR>3.
若某串的长度小于一个常数，则采用 存储方式最省空间。<BR>4. 对矩阵采用压缩存储是为了 。<BR>5.
数组A[1..10,1..10]的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5,6]的地址为
。<BR>6.
已知数组A[1..10,1..10]为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先存储在起始地址为1000的连续内存单元中，则元素A[5，6]对应的地址为
。<BR>7.
将下三角矩阵A[1..8,1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7,5]的地址为
。<BR>8.
已知数组A[1..10,0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5,9]的地址是
。<BR>9. 有n个球队参加的足球联赛按主客场制进行比赛，共需进行 场比赛。
<P>查找、排序<BR>1．设散列函数为H（key），用拉链（链地址）法解决冲突，Ｈ的值域为0,…,n-1，构造的散列表类型如下：<BR>type
link=↑node;<BR>node=record<BR>key:keytype;<BR>next:link;<BR>……<BR>end;<BR>Openhash=array[0..n-1]
of
link；<BR>请在下列算法划线处填上适当内容，以完成在散列表HP中查找键值等于K的结点，若查找成功，返回该结点的指针,否则返回空指针。<BR>Function
research(K:keytype;HP<IMG
src="数据结构热身题之填空题 - 考研论坛.files/redface.gif">penhash):link；<BR> begin<BR> i:=H(K)；SUC:=false；
；<BR>while (P<>NIL) and (not SUC) do <BR>if P↑.key<>K
then <BR> else SUC:=true；<BR>return(P)<BR>end；<BR>2.
二叉排序树的结点及指针类型如示，请在下面算法空框内填上适当内容，以完成在二叉排序树t中查找键值为k的结点。<BR>Type
bitre=↑bnode; <BR>bnode=record<BR>data<IMG
src="数据结构热身题之填空题 - 考研论坛.files/biggrin.gif">atatype;<BR>Lchild,Rchild:bitre<BR>end;<BR>Function
search(t:bitre;k<IMG
src="数据结构热身题之填空题 - 考研论坛.files/biggrin.gif">atatype):bitre;<BR>/*在t中查找键值为k的结点，成功时返回该结点的指针，否则返回nil*/<BR>begin<BR>if
t=nil then return(t) <BR>else
case<BR>t↑.data=k:return(t);<BR>t↑.data>k: ;<BR>t↑.data<k:
;<BR>end<BR>end;<BR>3. 对有17个元素的有序表A[1..17]做二分查找，在查找值等于A的元素时，被比较的元素的下标依次为
。<BR>4. 在按关键字递增的数组A[1..20]中，用二分查找方法进行查找时，查找长度为5的元素个数是 。<BR>5.
分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增序列的表递增顺序排序，最省时间的是 算法，最费时间的是 算法。<BR>6.
下列排序算法中，占用辅助空间最多的是 （堆，希尔，快速，归并）排序。<BR>7.
下列排序算法中，稳定的排序算法是（选择，堆，快速，直接插入）排序。<BR>8. 冒泡排序算法在最好情况下的元素交换次数为 。<BR>9.
直接选择排序算法所执行的元素交换次数最多为 次。<BR>0. 直接选择排序算法在最好情况下所作的交换元素的次数为 。<BR>1.
已知一个待排序序列已基本有序（每个元素离最终位置不远），则采用下列排序算法中的 最省时间（直接选择排序，堆排序，直接插入排序，快速排序）。
<P>树、二叉树<BR>1. 3个结点可构成 棵不同形态的树。<BR>2. 树 t 的存储结构为二叉链表bt，树t中的一个非叶子结点在bt中满足条件
。<BR>3. 在二叉链表中，判断某指针P所指结点为叶子结点的条件 。<BR>4.
一棵树T采用二叉链表BT存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定满足 。<BR>5. 在顺序存储的二叉树中，编号为 i
和 j 的两个结点处在同一层的条件是 。<BR>6.
对于给出的二叉树，按中序历遍所得到的结点序列为 。<BR>A<BR><BR>B C<BR><BR>D E
F<BR><BR>H<BR>7. 已知二叉树有50个叶子结点，则该二叉树的总结点数至少是 。<BR>8.
已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为 。<BR>9. 已知完全二叉树的第7层有8个结点，则其叶子结点数是
。<BR>0. 已知完全二叉树的第7层有10个叶子结点，则整个二叉树的结点数最多是 。 <BR>1.
在左右子树均不空的先序线索二叉树中，空链域的数目是 。<BR>2. 有n个结点的并且高度为n的二叉树的数目是
。<BR>3．具有100个结点的完全二叉树的深度为 。<BR>4. 高度为7的平衡二叉树至少有 个结点。<BR>5.
高度为8的平衡二叉树的结点数至少是 。<BR>6. 高度为5的三阶B树至少有 个结点。<BR>7.
已知完全二叉树的第八层有8个结点，则其叶子结点数是 。<BR>8. 若以{4,5,6,7,8}作为叶子结点的权值改造哈夫曼树，则其带权路径长度是
。<BR>9. 在有n个叶子结点的哈夫曼树中，总结点数是 。<BR>0. 高为k的m阶B树至少有 个结点。<BR>图<BR>1.
在有n个结点的无向图中，其边数最多/少为 / 。<BR>2. 在有n个结点的有向图中，每个结点的度最大可达 。<BR>3.
设有向图G的邻接矩阵为A，如果图中不存在弧〈Vi,Vj〉，则A[i,j]的值为
。<BR>4．有向图G用邻接矩阵A存储，其第i行的所有元素之和是该结点i的 。<BR>5. 有n个结点的有向图G最多有 条弧。<BR>6.
有n个结点的连通图至少有 条边。<BR>7. 有n个结点的强连通有向图G至少有 条弧。<BR>8. 如果含有n个结点的图是一个环，则它有
棵生成树。<BR>9. 求最短路径的Dijkstra算法的时间复杂度为 。<BR>
<P>
<HR>
做人如果没梦想，那跟咸鱼有什么分别？ </TD></TR>
<TR bgColor=#f7f7f7>
<TD vAlign=top noWrap width="18%">zhushuji<BR><IMG
src="数据结构热身题之填空题 - 考研论坛.files/user.gif"
vspace=5><BR><B>一般站友</B><BR>积分：152<BR>发贴：41<BR>来自：guangdong<BR>注册：2000-08-28<BR></TD>
<TD vAlign=top><IMG src="数据结构热身题之填空题 - 考研论坛.files/icon1.gif"
align=absMiddle border=0> 发表于 2001-12-25 <FONT
color=#000000>22:32:36</FONT> <A target=_blank
href="http://bbs.kaoyan.com/viewuser.asp?username=zhushuji"><IMG
alt=按此观看zhushuji的个人资料 src="数据结构热身题之填空题 - 考研论坛.files/profile.gif"
align=absMiddle border=0></A> <IMG alt=该用户不允许显示它的电子邮件
src="数据结构热身题之填空题 - 考研论坛.files/email.gif" align=absMiddle border=0> <A
href="http://bbs.kaoyan.com/pm.asp?action=newPM&recipient=zhushuji&subject=%CA%FD%BE%DD%BD%E1%B9%B9%C8%C8%C9%ED%CC%E2%D6%AE%CC%EE%BF%D5%CC%E2"><IMG
alt=发送悄悄话给zhushuji src="数据结构热身题之填空题 - 考研论坛.files/pm.gif" align=absMiddle
border=0></A> <A target=_blank
href="http://bbs.kaoyan.com/search.asp?action=searchuser&username=zhushuji"><IMG
height=16 alt=搜索zhushuji的所有帖子 src="数据结构热身题之填空题 - 考研论坛.files/find.gif"
width=16 align=absMiddle border=0></A> <A
href="http://bbs.kaoyan.com/posting.asp?Forum=%BC%C6%CB%E3%BB%FA&Topic=608552&TopicSubject=%CA%FD%BE%DD%BD%E1%B9%B9%C8%C8%C9%ED%CC%E2%D6%AE%CC%EE%BF%D5%CC%E2&action=editpost"><IMG
alt=编辑/删除帖子 src="数据结构热身题之填空题 - 考研论坛.files/edit.gif" align=absMiddle
border=0 ?></A> <A
href="http://bbs.kaoyan.com/posting.asp?quotenum=608552&action=replywquote&forum=%BC%C6%CB%E3%BB%FA&topic=608127&TopicSubject=%CA%FD%BE%DD%BD%E1%B9%B9%C8%C8%C9%ED%CC%E2%D6%AE%CC%EE%BF%D5%CC%E2"><IMG
alt=引用这个帖子回复 src="数据结构热身题之填空题 - 考研论坛.files/quote.gif" align=absMiddle
border=0></A> <A
href="http://bbs.kaoyan.com/posting.asp?action=copypost&topic=608552"><IMG
alt=复制 src="数据结构热身题之填空题 - 考研论坛.files/copy.gif" align=absMiddle
border=0></A> <A
href="http://bbs.kaoyan.com/download.asp?topic=608552"><IMG
alt=将本帖子内容通过email打包下载 src="数据结构热身题之填空题 - 考研论坛.files/mailto.gif"
align=absMiddle border=0></A> <A
href="http://bbs.kaoyan.com/ubbmisc.asp?forum=%BC%C6%CB%E3%BB%FA&action=getip&topic=608552"><IMG
alt=管理员查看zhushuji的IP src="数据结构热身题之填空题 - 考研论坛.files/ip.gif" align=absMiddle
border=0></A>
<HR>
<DIV align=right></DIV>题挺好！
<P>
<HR>
Let us do better.<BR></TD></TR></TBODY></TABLE>
<TABLE width="100%" border=0>
<TBODY>
<TR>
<TD></TD>
<TD align=right><A
href="http://bbs.kaoyan.com/newsDetail.asp?action=findthread&Forum=%BC%C6%CB%E3%BB%FA&go=newer&id=608127">上一贴</A> | <A
href="http://bbs.kaoyan.com/newsDetail.asp?action=findthread&Forum=%BC%C6%CB%E3%BB%FA&go=older&id=608127">下一贴</A></TD></TR></TBODY></TABLE>
<TABLE width="100%" border=0>
<TBODY>
<TR>
<TD align=middle><B>管理选项：</B><A
href="http://bbs.kaoyan.com/Posting.asp?action=CloseThread&topic=608127&topicsubject=%CA%FD%BE%DD%BD%E1%B9%B9%C8%C8%C9%ED%CC%E2%D6%AE%CC%EE%BF%D5%CC%E2&Forum=%BC%C6%CB%E3%BB%FA">关闭主题</A> | <A
href="http://bbs.kaoyan.com/posting.asp?action=movetotop&topic=608127&topicsubject=%CA%FD%BE%DD%BD%E1%B9%B9%C8%C8%C9%ED%CC%E2%D6%AE%CC%EE%BF%D5%CC%E2&forum=%BC%C6%CB%E3%BB%FA">置于顶部</A> | <A
href="http://bbs.kaoyan.com/archive.asp?action=transfer&topic=608127&topicsubject=%CA%FD%BE%DD%BD%E1%B9%B9%C8%C8%C9%ED%CC%E2%D6%AE%CC%EE%BF%D5%CC%E2&forum=%BC%C6%CB%E3%BB%FA">移动/归档</A> | <A
href="http://bbs.kaoyan.com/posting.asp?action=deletepost&topic=608127&topicsubject=%CA%FD%BE%DD%BD%E1%B9%B9%C8%C8%C9%ED%CC%E2%D6%AE%CC%EE%BF%D5%CC%E2&forum=%BC%C6%CB%E3%BB%FA">删除主题</A> </TD></TR>
<TR>
<TD>
<P><A
href="http://bbs.kaoyan.com/posting.asp?action=newtopic&forum=%BC%C6%CB%E3%BB%FA"><IMG
alt=新开主题 src="数据结构热身题之填空题 - 考研论坛.files/postnew.gif"
border=0></A> <A
href="http://bbs.kaoyan.com/posting.asp?action=reply&topic=608127&Forum=%BC%C6%CB%E3%BB%FA&TopicSubject=%CA%FD%BE%DD%BD%E1%B9%B9%C8%C8%C9%ED%CC%E2%D6%AE%CC%EE%BF%D5%CC%E2"><IMG
alt=回复该主题 src="数据结构热身题之填空题 - 考研论坛.files/replynew.gif"
border=0></A><BR></P></TD></TR></TBODY></TABLE>
<TABLE width="100%">
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -