《数据结构习题(无答案)》由会员分享，可在线阅读，更多相关《数据结构习题(无答案)（9页珍藏版）》请在金锄头文库上搜索。
1、习题第1章习题一、选择题1、下列关于算法的说法，正确的是 。A.算法的可行性是指指令不能有二义性B.算法最终必须由计算机程序实现C.程序一定是算法D.为解决某问题的算法与为该问题编写的程序含义是相同的2、以下关于数据的存储结构的叙述中，正确的有 。A.顺序存储方式只能用于存储线性结构B.顺序存储方式的优点是存储密度大，且插入、删除运算效率高C.链表的每个节点中都恰好包含一个指针D.散列法存储的基本思想是由关键字的值决定数据的存储地址E.散列表的节点只包含数据元素自身的信息，不包含任何指针3、下列说法正确的是 。A.数据元素是具有独立意义的最小标识单位B.原子类型的值不可再分解C.原子类型的值由
2、若干个数据项值组成D.结构类型的值不可以再分解二、判断题1、数据项是具有独立含义的最小标识单位。 2、数据的逻辑结构是指各数据元素之间的逻辑关系，与物理结构无关。 3、运算的定义依赖于逻辑结构，运算的实现也依赖于逻辑结构，而与存储结构无关。 4、数据结构是指相互之间存在一种或多种关系的数据元素的全体。 三、填空题1、数据的逻辑结构被分为 、 、 、 四种。2、当问题规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的 。3、时间复杂度在最好和最坏情况下分别是 和 。4、通常从正确性、 、 及时空效率等四个方面评价算法的质量。5、数据的存储结构主要有顺序存储、 、 和 四种。四、算法设计
3、1、写一算法，从键盘输入若干个非0整数（以0作为结束标志），找出其中最大和最小的数，并分析算法的时间复杂度（输入数据不需保存）。2、在数组A1.n中查找值为K的元素，若找到则输出其位置i（1in），否则输出0作为没有找到的标志，并分析算法的时间复杂度。第2章习题一、选择题1、线性表在链式存储中，各结点之间的地址是 。A.必须连续 B.部分地址必须连续 C.不能连续 D.连续与否无所谓2、对单链表表示法，以下说法错误的是 。A.数据域用于存储线性表的一个数据元素 B.指针域用于存放直接后继结点的指针C.所有数据通过指针的链接而组成单链表 D.单链表中各结点地址不可能连续3、某线性表中最常用的操作
4、是在最后一个元素之后插入一个数据和删除第一个元素，则采用 存储方式最节省运算时间。A.单链表 B.仅有尾指针的单循环链表 C.双向链表 D.仅有头指针的单循环链表4、线性表（a1,a2,.,an）以链式方式存储时，访问第i个元素的时间复杂性为 。A.O(n) B.O(1) C.O(i) D.O(i-1)二、判断题1、顺序表可以用一维数组表示，因此顺序表与一维数组在结构上是一致的，可以通用。2、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。3、链式存储结构中，访问任何结点都必须从表头开始。 4、循环链表可以在尾部设置头指针。 三、填空题1、已知L是无表头结点的单链表，且P结点即不是
5、首结点，也不是尾结点，试在下述要求中填上适合的语句序列。（1）在P结点之后插入S结点语句序列 。 S-next=p-next;p-next=S;（2）在P结点之前插入S结点语句序列 。 pre=L;while(pre-next!=P) pre=pre-next;S-next=pre-next或P;pre-next=S;2、已知P结点是某双向链表中的中间结点，请填空。（1）在P结点之后插入S结点的语句序列 。 S-next=P-next; S-prior=P;P-next-prior=S;P-next=S;（2）删除P结点的直接后继结点的语句序列 。 Q-P-next;P-next=Q-next
6、;Q-next-prior=P;free(Q);四、算法设计1、设L为带头结点的单链表，编写算法，删除链表中值相同的元素，并分析算法时间复杂性。假设单链表L元素递增有序。2、已知递增有序的两个单链表A,B分别存储了一个集合。设计算法实现求两个集合的交集运算A=AB。第3章习题一、选择题1、栈与一般线性表的区别在于 。A.数据元素的类型不同 B.数据元素的个数不同 C.运算是否受限制 D.逻辑数据不同2、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s4,s3,s6,s5,s1，则栈的容量至少应该是 。A.3 B.4 C.5 D.63、若已知一个栈
7、的入栈序列是1,2,3,30，其输出序列是p1,p2,p3,pn，若p1=30，则p10为 。A.11 B.20 C.30 D.214、循环队列Am存放其元素，用front和rear分别表示队头及队尾，则循环队列满的条件是 。A.（Q-rear+1）%m = =Q-front B. Q-rear+1 = =Q-front C. Q-rear = =Q-front + 1 D. Q-rear = =Q-front5、设abcdef以所给的次序进栈，若在进栈操作时，允许出栈操作，则下面得不到的序列是 。A.fedcba B. cabdef C.dcefba D. bcafed二、判断题1、消除递归
8、一定需要使用栈。 2、栈与队列是一种特殊的线性表。 3、队列逻辑上是一端既能增加又能减少的线性表。 4、任何一个递归过程都可以转换为非递归过程。 三、填空题1、已知一个栈s的输入序列为abcd，判断下面两个序列能否通过的Push和Pop操作输出：（1）dbca 。 （2）cbda 。2、假设以S和X分别表示入栈和出栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列是 。3、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是 。四、算法设计1、已知Q是一个非空队列，S是一个空栈，仅用队列和栈的基本操作和少量工作变量，编写一个算法，将队列Q中的所
9、有元素逆置。2、假设称正读和反读都相同的字符序列为“回文”，例如“”、“abcdedcba”是回文，“asdasd”不是回文。试编写一个算法判断读入的一个以“”为结束符的字符序列是否为回文。第4、5章习题一、选择题1、下列关于串的叙述中，不正确的是 。A.串是字符的有限序列 B.模式匹配是串的一种重要运算 C.空串是由空格构成的串 D.串既可采用顺序存储，也可以采用链式存储2、已知串S=“aaab”，其next数组值为 。A.0,1,2,3 B.1,1,2,3 C.1,2,3,1 D.1,2,1,1 3、串ababaabab的next数组值为 。A.0,1,2,3,4,5,6,7,8 B.0,
10、1,1,2,3,4,5,3,4 C.0,1,2,1,2,1,1,1,2 D.0,1,2,3,0,1,2,2,2 4、在执行简单的串匹配算法时，最坏的情况为每次匹配比较不等的字符出现的位置为 。A.主串的最末字符 B.模式串的第一个字符C.主串的第一个字符 D. 模式串的最末字符二、判断题1、串是一种数据对象和操作都特殊的线性表。 2、空串与空格串是相同的。 3、KMP算法的特点是在模式匹配时指示主串的指针不会变小。 4、从串中取若干个字符组成的字符序列称为串的子串。 三、填空题1、两个串相等的充分必要条件是 。 串长度相等且对应位置上的字符也相等2、StrIndex(MY STUDENT,ST
11、U)= 。四、算法设计1、利用C的库函数strlen,strcpy写一算法void StrDelete（char *S,int i,int m）,删除串S中从位置i开始的连续m个字符。若istrlen（S），则没有字符被删除；若i+mstrlen（S），则将S中位置i开始直至末尾的字符都删去。2、设s,t为两个字符串，试写一算法判断t是否为s的子串。五、简答题求下面各广义表的操作结果。(1) GetHead(a,(b,c),d) (2) GetTail(a,(b,c),d) (3) GetHead(GetTail (a,(b,c),d) (4) GetTail (GetHead (a,(b,c
12、),d) 第6章习题一、选择题1、下面关于二叉树的描述中，正确的是 。A. 二叉树中，度为0的结点个数等于度为2的结点个数加1B. 完全二叉树中，任何一个结点的度或者为0，或者为2C. 二叉树中结点个数必大于0D. 二叉树的度为22、对一个满二叉树，m个树枝，n个结点，深度为h，则 。A. n=h+m B. h+m=2n C. m=h-1 D. n=2h-13、以二叉链表作为二叉树的存储结构，在有n个结点的二叉链表中（n0），链表中空链的个数为 。A. 2n-1 B. n-1 C. n+1 D. 2n+14、将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为 。A. 33 B. 34 C. 35 D. 365、在一棵二叉树结点的先序序列、中序序列、后序序列中，所有叶子结点的先后顺序 。A. 都不相同 B. 先序和中序相同，而与后序不同C. 完全相同 D. 中序和后序相同，而与先序不同6、一棵二叉树满足下列条件：对任意一个结点，若存在左、右子树，则其值都小于它的左子树上的所有结点的值，而大于右子树上所有结点的值。现采用 遍历方式就可以得到这棵二叉树上所有结点的递减序列。A. 先序
