《数据结构习题(无答案)》由会员分享,可在线阅读,更多相关《数据结构习题(无答案)(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. 先序