《数据结构》作业习题

《《数据结构》作业习题》由会员分享，可在线阅读，更多相关《《数据结构》作业习题（26页珍藏版）》请在金锄头文库上搜索。

1、数据结构数据结构作业习题作业习题汗水和丰收是忠实的朋友，勤学和知识是一对最美丽的恋人。数据结构精选习题集粹参考书目：1全国计算机技术与软件专业技术资格（水平）考试 2004、2005上半年试题分析与解答清华大学出版社2梁作娟等编著，数据结构习题解答与考试指导，清华大学出版社第 1 章 绪论判断：（中科院 1999）顺序存储方式只能用于存储线性结构。顺序查找法适用于存储结构为顺序或链接存储的线性表。错对填空：（中科院 1999）对于给定的 n 个元素，可以构造出的逻辑结构有（ ） 、 （ ） 、 （ ） 、 （ ）四种。集合线性结构树形结构图结构选择：（中科院 2001）计算机算法必须具备输入、

2、输出、 （ ）等 5 个特性。A.可行性、可移植性和可扩展性 B.可行性、确定性和有穷性C.确定性、有穷性和稳定性 D.易读性、安全性和稳定性B问答：（北京科技大学 2002）数据的逻辑结构在计算机存储中的映像（或表示）通常有几种方法？顺序映像和非顺序映像线性结构和树性结构的特点分别是什么？结构中的数据元素之间存在一个对一个的关系结构中的数据元素之间存在一个对多个的关系选择：（武汉理工 2002）算法在发生非法操作时可以作出处理的特性称为（ ）A.正确性 B.易读性 C.健壮性 D.可靠性C简答：（武汉理工 2002）简述顺序存储结构与链式存储结构在表示数据元素之间关系上的只要区别。用物理位置

3、相邻表示逻辑关系上的相邻用结点中的指针指示关系简答：（南京理工 2002）简述算法的 5 个特性。教材中的简述即可选择：（南京理工 2002）数据结构是一门研究非数值计算的程序设计问题中计算机的（ ）以及它们之间的（ ）和运算的学科。A.操作对象 B.计算方法 C.逻辑存储 D.数据映像A.结构 B.关系 C.运算 D.算法AB在数据结构中，逻辑上数据结构可分为：（ ）A.动态结构和静态结构 B.线性结构和非线性结构C.紧凑结构和非紧凑结构 D.内部结构和外部结构B名词解释：（武汉大学 2002）数据对象 物理结构 空间复杂度选择：（2005 程序员）数据结构主要研究数据的（ ）A.逻辑结构

4、B.存储结构 C.逻辑结构和存储结构 D.逻辑结构和存储结构及其运算的实现D选择；（2004 程序员）为了描述 n 个人之间的同学关系，可用（ ）结构表示A.线性表 B.树 C.图 D.队列B选择：（2004 软件设计师）下面的程序段违反了算法的（ ）原则void sam() int n=2;while (!odd(n) n+=2;printf(n);A.有穷性 B.确定性 C.可行性 D.健壮性A第 2 章 线性表选择：（清华大学 1998）线性表是具有 n 个（ ）的有限序列A.表元素 B.字符 C.数据元素 D.数据项 E.信息项C选择：（中国科技大学 1998）将两个各有 n 个元素的

5、有序表归并成一个有序表，其最少的比较次数是（ ）A.n B.2n-1 C.2n D.n-1A问答：（北京航空 1998）在非空双向循环表中 q 所指的结点后面插入 p 所指的结点的过程已经依次进行了 3 步：p-llink:=q；p-rlink:=q-rlink；q-rlink:=p；第 4 步应是什么动作？q-rlink.llink:=p汗水和丰收是忠实的朋友，勤学和知识是一对最美丽的恋人。问答：（北京航空 1998）若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？链式存储结构算法：（北京工业大学 1998）写出在双向链表 da 中的插入操作算法，算法中插入位置

6、的获取可以直接引用 getnodep(da,I)，其中参数 da 为双向链表，i 是要插入的数据，要求算法中含有双向链表 da 的结点结构描述。简答：（北京科技大学 2002）设单链表中结点的数据域为 data，指针域为 next，指针 p 为表中某一结点的地址，请写出在 p 结点之前插入一个 s 结点的 C 语言描述语句。s-.next:=p算法：（北京科技大学 2002）设有两个带头结点的单链表 A 和 B，链表中结点的数据域为data（整型） ，指针域为 next。请用 C 语言函数形式写出将表 A 和B 合并为一个单链表 L 的算法 Union(A，B，L)（注：若表 A 和 B 中有

7、数据值相同的结点，只保留其中一个）选择：（武汉理工 2002）指针 P 所指的元素是双向循环链表 L 的尾元素的条件是（ ）A.P=L B.P=NULL C.P-Link=L D.P-Rlink=LD判断：（武汉理工 2002）一个循环链表可以由所给定的头指针或者尾指针惟一地确定。对算法：（武汉理工 2002）写一个算法，建立双向循环链表简答：（南京理工 2002）写出在双向链表指针 P 之后插入结点 S 的操作序列s-right=p-right；if(p-right) p-right-left=s； s-left=p； p-right=s选择：（南京理工 2002）在一个单链表中，若删除 P

8、 结点的后继结点，则（ ）A.p-next=p-next-next B.p=p-next；p-next=p-next-next;C.p-next=p-next;D.p=p-next-next;A选择：（软件设计师 2005）循环链表的主要优点是（ ）A.不再需要头指针了 B.已知某个结点的位置后，能很容易找到它的直接前驱结点C.在进行删除操作后，能保证链表不断开D.从表中任一结点出发都能遍历整个链表D第 3 章 栈和队列选择：（程序员 2005）PUSH 和 POP 命令常用于（ ）操作A.队列 B.数组 C.栈 D.记录C选择：（程序员 2004）判断一个表达式中左右括号是否匹配，采用（ ）

9、实现较为方便A.线性表的顺序存储 B.队列 C.线性表的链式存储 D.栈D选择：（清华大学 1998）用单链表表示的链式队列的对头在链表的（ ）位置A.链头 B.链尾 C.链中A判断：（中科院 1999）栈和队列都是限制取点的线性结构正确判断：（中国科技大学 1998）消除递归不一定需要使用栈正确判断：（清华大学 2002）栈、先进先出队列、优先级队列、双端队列等都可以看作是一个容器类的派生类。该容器代表限制存取位置的顺序存取结构。正确算法：（中科院 2000）设顺序栈 S 中有 2n 个元素，从栈顶到栈底的元素依次是 a2n，a2n-1， 。 。 。 ，a2，a1，要求通过一个辅助的循环队列

10、及相应的入栈、出栈、入队、出队操作来重新排列栈中元素，使得从栈顶到栈底的元素依次是 a2n，a2n-2， 。 。 。 ，a4，a2，a2n-1，a2n-3， 。 。 。 ，a3，a1，请写出一算法实现该操作，要求附加的空间是 O(n)，时间复杂度为 O(n)。选择：（中科院 2000）设栈的输入序列是 1,2,3,4，则（ ）不可能是其出栈序列A.1,2,4,3 B.2,1,3,4 C.1,4,3,2 D.4,3,1,2 E.3,2,1,4D简答：（武汉理工 2002）A、B、C 三个元素进栈 S 的次序是 A、B、C，利用 Push(S,X)，Pop(S)表示入栈、出栈操作，写出所有可能的出

11、栈序列和获得每个序列的相应操作，并指明哪个序列不会是出栈序列。CBA BCA ACB ABC BACCAB简答：（南京理工 2002）在操作序列 push(1)，push(2)，pop，push(5)，push(7)，pop，push(6)之后，栈顶元素和栈底元素分别是什么？61简答：（南京理工 2002）在操作序列 Qinsert(1)，Qinsert(2)，Qdelete，Qinsert(5)，Qinsert(7)，Qdelete，Qinsert(9)之后，队头元素和队尾元素分别是什么？59选择；（南京理工 2002）循环队列 A0.m-1存放其元素，用 front 和 rear 分别表示

12、队头和队尾，则循环队列满的条件是（ ）A.（Q.rear+1）%m=Q.front B.Q.rear=Q.front+1汗水和丰收是忠实的朋友，勤学和知识是一对最美丽的恋人。C.Q.rear+1=Q.front D.Q.rear=Q.frontA选择：一般情况下，将递归算法转换成等价的非递归算法应该设置（ ）A.堆栈 B.队列 C.堆栈和队列 D.数组A第 4 章 串选择：（程序员 2004）字符串是一种线性表，其特殊性表现在（ ）A.它的数据元素是一个字符 B.它可以链式存储C.它可以顺序存储 D.它的数据元素可以是多个字符A简答：（清华大学 1998）设目标为 S=“abcaabbcaaa

13、bababaabca“，模式为 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=

14、substring(s,i2,strlenght(s)-i2+1);t3=concat(t1,t2);设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作（ ）A.连接 B.模式匹配 C.求子串 D.求串长B设 s1ABCDEFG，s2PQRST，con(subs(s1,2,len(s2), subs(s1,len(s2),2)的结果串是（ ）A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEFD已知 athis，b ，cgood，dne，fa sample，gissconcat(a, concat(substr(f,2,7), concat(b, subst

15、r(a,3,2)treplace(f, substr(f,3,6), c)uconcat(substr(c,3,1), d)vconcat(s, concat(b, concat(t, concat(b, u)试问：s, t, u, v, length(s), index(v,g), index(u,g)各是什么？sthis sample ist a good oneuonevthis sample is a good onelength(s)=14index(v,g)=3index(u,g)=0第 5 章 数组和广义表选择：（程序员 2005）设数组 a1.10,5.15的元素以行为主序存放，每个元素占用 4 个存储单元，则数组元素 ai,j