《《数据结构》作业习题42786.doc》由会员分享，可在线阅读，更多相关《《数据结构》作业习题42786.doc（25页珍藏版）》请在金锄头文库上搜索。
1、数据结构作业习题42786最珍贵的财富是时间，最大的浪费是虚度流年。数据结构精选习题集粹参考书目：1全国计算机技术与软件专业技术资格（水平）考试2004、2005上半年试题分析与解答 清华大学出版社2梁作娟等编著，数据结构习题解答与考试指导，清华大学出版社第1章 绪论判断：（中科院1999）顺序存储方式只能用于存储线性结构。顺序查找法适用于存储结构为顺序或链接存储的线性表。错对填空：（中科院1999）对于给定的n个元素，可以构造出的逻辑结构有（ ）、（ ）、（ ）、（ ）四种。集合线性结构树形结构图结构选择：（中科院2001）计算机算法必须具备输入、输出、（ ）等5个特性。A.可行性、可移植性
2、和可扩展性 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.逻辑结构 B.存储结构 C.逻辑结构和存储结构 D.逻辑结构和存储结构及其运算
4、的实现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个元素的有序表归并成一个有序表，其最少的比较次数是（ ）A.n B.2n-1 C.2n D.n-
5、1A问答：（北京航空1998）在非空双向循环表中q所指的结点后面插入p所指的结点的过程已经依次进行了3步：p-llink:=q；p-rlink:=q-rlink；q-rlink:=p；第4步应是什么动作？q-rlink.llink:=p 最珍贵的财富是时间，最大的浪费是虚度流年。问答：（北京航空1998）若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？链式存储结构算法：（北京工业大学1998）写出在双向链表da中的插入操作算法，算法中插入位置的获取可以直接引用getnodep(da,I)，其中参数da为双向链表，i是要插入的数据，要求算法中含有双向链表da的结点结
6、构描述。简答：（北京科技大学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中有数据值相同的结点，只保留其中一个）选择：（武汉理工2002）指针P所指的元素是双向循环链表L的尾元素的条件是（ ）A.P=L B.P=NULL C.P-Link=L D.P-Rlink=LD判断
7、：（武汉理工2002）一个循环链表可以由所给定的头指针或者尾指针惟一地确定。对算法：（武汉理工2002）写一个算法，建立双向循环链表简答：（南京理工2002）写出在双向链表指针P之后插入结点S的操作序列s-right=p-right；if(p-right) p-right-left=s； s-left=p； p-right=s选择：（南京理工2002）在一个单链表中，若删除P结点的后继结点，则（）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）循环
8、链表的主要优点是（ ）A.不再需要头指针了 B.已知某个结点的位置后，能很容易找到它的直接前驱结点C.在进行删除操作后，能保证链表不断开D.从表中任一结点出发都能遍历整个链表D第3章 栈和队列选择：（程序员2005）PUSH和POP命令常用于（ ）操作A.队列 B.数组 C.栈 D.记录C选择：（程序员2004）判断一个表达式中左右括号是否匹配，采用（ ）实现较为方便A.线性表的顺序存储 B.队列 C.线性表的链式存储 D.栈D选择：（清华大学1998）用单链表表示的链式队列的对头在链表的（ ）位置A.链头 B.链尾 C.链中A判断：（中科院1999）栈和队列都是限制取点的线性结构正确判断：（
9、中国科技大学1998）消除递归不一定需要使用栈正确判断：（清华大学2002）栈、先进先出队列、优先级队列、双端队列等都可以看作是一个容器类的派生类。该容器代表限制存取位置的顺序存取结构。正确算法：（中科院2000）设顺序栈S中有2n个元素，从栈顶到栈底的元素依次是a2n，a2n-1，。，a2，a1，要求通过一个辅助的循环队列及相应的入栈、出栈、入队、出队操作来重新排列栈中元素，使得从栈顶到栈底的元素依次是a2n，a2n-2，。，a4，a2，a2n-1，a2n-3，。，a3，a1，请写出一算法实现该操作，要求附加的空间是O(n)，时间复杂度为O(n)。选择：（中科院2000）设栈的输入序列是1,
10、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)表示入栈、出栈操作，写出所有可能的出栈序列和获得每个序列的相应操作，并指明哪个序列不会是出栈序列。CBA BCA ACB ABC BACCAB简答：（南京理工2002）在操作序列push(1)，push(2)，pop，push(5)，push(7)，pop，push(6)之后，栈顶元素和栈底元素分别是什么？61简答：（南京理工2002）在操作序列Qins
11、ert(1)，Qinsert(2)，Qdelete，Qinsert(5)，Qinsert(7)，Qdelete，Qinsert(9)之后，队头元素和队尾元素分别是什么？59选择；（南京理工2002）循环队列A0.m-1存放其元素，用front和rear分别表示队头和队尾，则循环队列满的条件是（ ）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.
12、数组A第4章 串选择：（程序员2004）字符串是一种线性表，其特殊性表现在（ ）A.它的数据元素是一个字符 B.它可以链式存储C.它可以顺序存储 D.它的数据元素可以是多个字符A简答：（清华大学1998）设目标为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。要求写出得到
13、上述结果串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.求串长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(su
