数据结构作业习题文档格式.doc
《数据结构作业习题文档格式.doc》由会员分享，可在线阅读，更多相关《数据结构作业习题文档格式.doc（26页珍藏版）》请在冰点文库上搜索。
－C
简答：
简述顺序存储结构与链式存储结构在表示数据元素之间关系上的只要区别。
－用物理位置相邻表示逻辑关系上的相邻
－用结点中的指针指示关系
（南京理工2002）
简述算法的5个特性。
－教材中的简述即可
数据结构是一门研究非数值计算的程序设计问题中计算机的（）以及它们之间的（）和运算的学科。
A.操作对象B.计算方法C.逻辑存储D.数据映像
A.结构B.关系C.运算D.算法
－A
在数据结构中，逻辑上数据结构可分为：
（）
A.动态结构和静态结构B.线性结构和非线性结构
C.紧凑结构和非紧凑结构D.内部结构和外部结构
名词解释：
（武汉大学2002）
数据对象物理结构空间复杂度
（2005程序员）
数据结构主要研究数据的（）
A.逻辑结构B.存储结构
C.逻辑结构和存储结构D.逻辑结构和存储结构及其运算的实现
－D
选择；
（2004程序员）
为了描述n个人之间的同学关系，可用（）结构表示
A.线性表B.树C.图D.队列
（2004软件设计师）
下面的程序段违反了算法的（）原则
voidsam（）
{intn=2;
while（!
odd（n））n+=2;
printf（n）;
}
A.有穷性B.确定性C.可行性D.健壮性
第2章线性表
（清华大学1998）
线性表是具有n个（）的有限序列
A.表元素B.字符C.数据元素D.数据项E.信息项
（中国科技大学1998）
将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）
A.nB.2n-1C.2nD.n-1
（北京航空1998）
在非空双向循环表中q所指的结点后面插入p所指的结点的过程已经依次进行了3步：
p->
llink:
=q；
rlink:
=q->
rlink；
q->
=p；
第4步应是什么动作？
－q->
rlink.llink:
=p
汗水和丰收是忠实的朋友，勤学和知识是一对最美丽的恋人。
若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？
为什么？
－链式存储结构
算法：
（北京工业大学1998）
写出在双向链表da中的插入操作算法，算法中插入位置的获取可以直接引用getnodep（da,I），其中参数da为双向链表，i是要插入的数据，要求算法中含有双向链表da的结点结构描述。
设单链表中结点的数据域为data，指针域为next，指针p为表中某一结点的地址，请写出在p结点之前插入一个s结点的C语言描述语句。
－s->
.next:
设有两个带头结点的单链表A和B，链表中结点的数据域为data（整型），指针域为next。
请用C语言函数形式写出将表A和B合并为一个单链表L的算法Union（A，B，L）（注：
若表A和B中有数据值相同的结点，只保留其中一个）
指针P所指的元素是双向循环链表L的尾元素的条件是（）
A.P=LB.P=NULLC.P->
Link=LD.P->
Rlink=L
一个循环链表可以由所给定的头指针或者尾指针惟一地确定。
写一个算法，建立双向循环链表
写出在双向链表指针P之后插入结点S的操作序列
right=p->
right；
if（p->
right）p->
right->
left=s；
s->
left=p；
p->
right=s
在一个单链表中，若删除P结点的后继结点，则（ ）
A.p->
next=p->
next->
next
B.p=p->
next；
next;
C.p->
D.p=p->
（软件设计师2005）
循环链表的主要优点是（）
A.不再需要头指针了
B.已知某个结点的位置后，能很容易找到它的直接前驱结点
C.在进行删除操作后，能保证链表不断开
D.从表中任一结点出发都能遍历整个链表
第3章栈和队列
（程序员2005）
PUSH和POP命令常用于（）操作
A.队列B.数组C.栈D.记录
（程序员2004）
判断一个表达式中左右括号是否匹配，采用（）实现较为方便
A.线性表的顺序存储B.队列C.线性表的链式存储D.栈
用单链表表示的链式队列的对头在链表的（）位置
A.链头B.链尾C.链中
栈和队列都是限制取点的线性结构
－正确
消除递归不一定需要使用栈
（清华大学2002）
栈、先进先出队列、优先级队列、双端队列等都可以看作是一个容器类的派生类。
该容器代表限制存取位置的顺序存取结构。
（中科院2000）
设顺序栈S中有2n个元素，从栈顶到栈底的元素依次是a2n，a2n-1，。
。
，a2，a1，要求通过一个辅助的循环队列及相应的入栈、出栈、入队、出队操作来重新排列栈中元素，使得从栈顶到栈底的元素依次是a2n，a2n-2，。
，a4，a2，a2n-1，a2n-3，。
，a3，a1，请写出一算法实现该操作，要求附加的空间是O（n），时间复杂度为O（n）。
设栈的输入序列是1,2,3,4，则（）不可能是其出栈序列
A.1,2,4,3B.2,1,3,4C.1,4,3,2D.4,3,1,2E.3,2,1,4
A、B、C三个元素进栈S的次序是A、B、C，利用Push（S,X），Pop（S）表示入栈、出栈操作，写出所有可能的出栈序列和获得每个序列的相应操作，并指明哪个序列不会是出栈序列。
－CBABCAACBABCBAC
－CAB
在操作序列push
（1），push
（2），pop，push（5），push（7），pop，push（6）之后，栈顶元素和栈底元素分别是什么？
－6
－1
在操作序列Qinsert
（1），Qinsert
（2），Qdelete，Qinsert（5），Qinsert（7），Qdelete，Qinsert（9）之后，队头元素和队尾元素分别是什么？
－5
－9
循环队列A[0..m-1]存放其元素，用front和rear分别表示队头和队尾，则循环队列满的条件是（）
A.（Q.rear+1）%m==Q.frontB.Q.rear==Q.front+1
C.Q.rear+1==Q.frontD.Q.rear==Q.front
一般情况下，将递归算法转换成等价的非递归算法应该设置（）
A.堆栈B.队列C.堆栈和队列D.数组
第4章串
字符串是一种线性表，其特殊性表现在（）
A.它的数据元素是一个字符B.它可以链式存储
C.它可以顺序存储D.它的数据元素可以是多个字符
设目标为S="
abcaabbcaaabababaabca"
，模式为P="
babab"
，
（1）手工计算P的nextval值；
（2）写出利用求得的nextval数组，按KMP算法对目标S进行模式匹配的过程。
（东北大学1998）
已知3个字符串分别为S='
ab...abcaabcbca...a'
，S1='
caab'
，S2='
bcb'
，利用所学字符串基本运算的函数得到结果串为：
S3='
caabcbca....aca...a'
要求写出得到上述结果串S所用的函数及执行算法。
－算法核心部分：
i1=index（s,s1,1）；
i2=index（s,s2,1）+3;
t1=substring（s,i1,strlength（s）-i1+1）;
t2=substring（s,i2,strlenght（s）-i2+1）;
t3=concat（t1,t2）;
设有两个串p和q，求q在p中首次出现的位置的运算称作（）
A.连接B.模式匹配C.求子串D.求串长
设s1＝'
ABCDEFG'
，s2＝'
PQRST'
，con（subs（s1,2,len（s2））,subs（s1,len（s2）,2））的结果串是（）
A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF
已知a＝'
this'
，b＝'
'
，c＝'
good'
，d＝'
ne'
，f＝'
asample'
，g＝'
is'
s＝concat（a,concat（substr（f,2,7）,concat（b,substr（a,3,2））））
t＝replace（f,substr（f,3,6）,c）
u＝concat（substr（c,3,1）,d）
v＝concat（s,concat（b,concat（t,concat（b,u））））
试问：
s,t,u,v,length（s）,index（v,g）,index（u,g）各是什么？
－
s＝'
thissampleis'
t＝'
agoodone'
u＝'
one'
v＝'
thissampleisagoodone'
length（s）=14
index（v,g）=3
index（u,g）=0
第5章数组和广义表
设数组a[1..10,5..15]的元素以行为主序存放，每个元素占用4个存储单元，则数组元素a[i,j]（1≤i≤10,5≤j≤15）的地址计算公式为（）
A.a-204+2i+jB.a-204+40i+4jC.a-84+i+jD.a-64+44i+4j
对于二维数组A[1..4,3..6]，设每个元素占两个存储单元，若分别以行和列为主序存储，则元素A[3,4]相对于数组空间起始地址的偏移量分别是（）和（）
A.12B.14C.16D.18
（软件设计师2004）
若广义表L=（（1,2,3）），则L的长度和深度分别是（）
A.1和1B.1和2C.1和3D.2和2
设广义表L=（（）,（）），则Head（L）=（）；
Tail（L）＝（）；
L的长度是（）；
L的深度是（）
－Head（L）=（）;
－Tail（L）=（（））;
－2
（北京邮电1998）
已知广义表L=（（x,y,z）,a,（u,t,w）），从L表中取出原子项t的运算是（）
A.head（tail（tail（L）））B.tail（head（head（tail（L））））
C.head（tail（head（tail（L））））D.head（tail（head（tail（tail（L）））））
将一个A[1..100,1..100]的三对角矩阵，按行优先存入一维数组B[1..298]中，A中元素A66,65（即元素下标）在B中的位置K为（）
A.198B.195C.197
三对角线矩阵A[1..n][1..n]以行序为主顺序存储，其存储始址是B，每个元素占一个存储单元，则元素A[i][j]的存储起始地址为（）（1≤i,j≤n）
A.b+2*j+i-2B.b+2*i+j-2C.b+2*j+i-3D.b+2*i+j-3
设字符串S满足concat（head（S）,head（tail（tail（S））））="
ac"
，则S=（）
A."
aabc"
B."
acbc"
C."
accc"
D."
acac"
第6章树和二叉树
在一颗非空二叉树中，叶子节点的总数比度为2的节点总数多（）个
A.-1B.0C.1D.2
在一棵完全二叉树中，其根的序号为1，（）可判定序号为p和q的两个结点是否在同一层。
A.│log2p」=│log2q」B.log2p=log2q
C.│log2p」+1=│log2q」D.│log2p」=│log2q」+1
如果根的层次为1，具有61个结点的完全二叉树的高度为（）
A.5B.6C.7D.8
若二叉树的先序遍历序列为ABDECF，中序遍历序列DBEAFC，则其后序遍历序列为（）
A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA
由权值为9,2,5,7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）
A.23B.37C.44D.46
假设先根次序遍历某棵树的结点次序为SACEFBDGHIJK，后根次序遍历该树的结点次序为CFEABHGIKJDS，要求画出这棵树。
（）的遍历仍需要栈的支持
A.前序线索树B.中序线索树C.后序线索树
（中国科技大学1999）（南京理工2002）
对于前序遍历和中序遍历结果相同的二叉树为（）；
对于前序遍历和后序遍历结果相同的二叉树为（）。
A.一般二叉树B.只有根结点的二叉树
C.根结点无左孩子的二叉树D.根结点无右孩子的二叉树
E.所有的结点只有左孩子的二叉树F.所有结点只有右孩子的二叉树
－F
（华北计算技术研究所2001）
将一棵树转化为二叉树后，根结点（）左子树
A.有B.没有
哈夫曼树是带权路径长度最短的树，路径上长度（）结点离根（）
A.较大B.较小C.较近D.较远
（中国人民大学2002）
简述二叉哈夫曼树的建树方法
设记录的关键字（key）集合K={26,36,41,44,15,68,12,6,51,25}，以K为权值集合，构建一棵哈夫曼树，依次取K中各值，构建一棵二叉排序树
判定：
高度为K的二叉树至多有2k-1（k≥1）个结点
－错误
Huffman树、平衡二叉树都是数据的逻辑结构
写出表达式a*（b+c）-d/e*f的后缀表达式
－abc+*de/f*-
画出有三个结点的所有二叉树
在线索化二叉树中，结点t没有左子树的充要条件是（）
A.t->
lchild=nullB.t->
ltag=1
C.t->
ltag=1且t->
lchild=nullD以上都不对
－B.
第7章图
采用邻接表表示一有向图，若图中某顶点的入度和出度分别为d1和d2，则该顶点对应的单链表的结点数为（）
A.d1B.d2C.d1-d2D.d1+d2
（程序员2005）（清华大学1998）
具有n（n>
0）个顶点的无向图最多含有（）条边
A.n（n-1）B.n（n+1）/2C.n（n-1）/2D.n（n+1）
无向图中一个顶点的度是指图中（）
A.通过该顶点的简单路径数B.通过该顶点的回路数
C.与该顶点相邻接的顶点数D.与该顶点连通的顶点数
一个具有n（n>
0）个顶点的连通无向图至少有（）条边
A.n+1B.nC.n/2D.n-1
无向图G=（V,A），其中V={a,b,c,d,e}，A={<
a,b>
<
a,c>
d,c>
d,e>
b,e>
c,e>
}，对该图进行拓朴排序，下面序列中哪一个不是拓朴序列
A.a,d,c,b,eB.d,a,b,c,eC.a,b,d,c,eD.a,b,c,e,d
试述一种判定有向图G中是否有圈（回路）的方法
－拓朴序列算法
不是所有的AOV网都有一个拓朴序列
每个加权连通无向图的最小生成树都是惟一的
邻接多重表示法对于有向图和无向图的存储都适用
一个加权连通无向图的最小生成树可以使用（）生成；
一项过程完工所需的最少时间等于某个（）
A.Hash算法B.Dijkstra算法C.Prim算法D.Huffman算法
A.AOE网中源点到汇点事件最多的路径的长度
B.AOE网中源点到汇点的最长路径的长度
C.AOE网中源点到汇点的最短路径的长度
D.AOE网中源点到汇点活动最多的路径的长度
构造无向连通网的最小生成树通常有哪两个典型的算法
－Prim算法和Kruskal算法
对下面所示的带权图，用普里姆算法画出该图的最小生成树的生成过程
当各边上的权值（）时，BFS算法可用来解决单源最短路径问题
A.均相等B.均互不相等C.不一定相等
kruskal算法的时间复杂度为（），它对（）图较为适合。
－O（eloge）
－稀疏
对下图所示的连通图，请画出：
（1）以顶点1为根的深度优先生成树；
（2）如果有关结点，请找出所有的关结点
－关结点：
1,2,3,7,8
第9章查找
利用逐点插入法建立序列（50,72,43,85,75,20,35,45,65,30）对应的二叉排序树以后，查找元素30要进行（）次元素间的比较
A.4B.5C.6D.7
在常用的描述二叉排序树的存储结构中，关键值最大的结点（）
A.左指针一定为空B.右指针一定为空C.左右指针均为空D.左右指针均不空
已知一个线性表（38,25,74,63,52
升级会员 