《经典数据结构习题集含答案》由会员分享，可在线阅读，更多相关《经典数据结构习题集含答案（7页珍藏版）》请在金锄头文库上搜索。
1、线性表1.下列有关线性表的叙述中，正确的是（ A ）。A）线性表中元素之间的关系是线性关系B）线性表中至少有一个元素C）线性表中的任一元素有且仅有一个直接前趋D）线性表中的任一元素有且仅有一个直接后继2.下述哪一条是顺序存储结构的优点？（A ）A）存储密度大 B）插入方便C）删除方便 D）可方便地用于各种逻辑结构的存储表示3.在一个长度为n的顺序表中，在第i个元素（1=inext = p-next; p-next = s;B）q-next = s; s-next = p;C）p-next = s; s-next = q;D）p-next = s-next; s-next = p;12.向一个有
2、115个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ C ）个元素。A) 115 B) 114 C) 58 D) 57 13.带头结点的单链表Head为空表的判定条件是 ( B ) 。A) Head-next=Head B) Head-next=NULLC) Head!=NULL D) Head=NULL14.若要求能快速地实现在链表的末尾插入结点和删除第一个结点的运算，则选择( B )最合适。A) 单链表 B) 带尾指针的单循环链表C) 双链表 D) 双循环链表15.给定有n个元素的向量，建立一个有序单链表的时间复杂度是( D )。A)O(n) B)O(log2n) C)O(
3、nlog2n) D. O(n2)16.线性表采用链式存储时，其地址( C)。A)必须是连续的 B)必须是不连续的C)连续与否均可 D)部分地址必须是连续的17.在一个具有n个结点的有序单链表中，插入一个新的结点并使之仍然有序的时间复杂度是(A )。A)O(n) B)O(log2n) C)O(1) D)O(n2) 排序1.在下列排序算法中，时间复杂度不受数据初始特性影响，恒为O(n2)的是（C ）。A）插入排序 B）冒泡排序 C）选择排序 D）堆排序2.在各种排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ C）。A）
4、希尔排序 B）冒泡排序 C）插入排序 D）选择排序3.快速排序方法在（C）情况下最不利于发挥其长处。A）要排序的数据量太大 B）要排序的数据含有多个相同值C）要排序的数据已基本有序 D）要排序的数据个数为奇数4.已知10个数据元素为(54,28,16,34,73,62,95,60,26,43),对该数列按从小到大排序，经过一趟冒泡排序后的序列为（B）。A）16，28，34，54，73，62，60，26，43，95B）28，16，34，54，62，73，60，26，43，95C）28，16，34，54，62，60，73，26，43，95D）16，28，34，54，62，60，73，26，43，9
5、55.一组记录的关键字为（46,79,56,38,40,84）,则利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为（ C ）。A）38,40,46,56,79,84 B）40,38,46,79,56,84 C）40,38,46,56,79,84 D）40,38,46,84,56,79 6.用某种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行排序时,元素序列的变化情况如下:(1)20,15,21,25,47,27,68,35,84 (2)15,20,21,25,35,27,47,68,84(3)15,20,21,25,27,35,47,68,84则所采
6、用的排序方法是（D ）。A）选择排序 B）希尔排序 C）归并排序 D）快速排序7.在待排序的元素序列基本有序的前提下，效率最高的排序方法是（A）。 A）插入排序 B）快速排序C）归并排序 D）选择排序8.一组记录的排序码为（20,29,11,74,35,3,8,56）,则利用堆排序方法建立的初始(小顶)堆为（B ）。A）20,29,11,74,35,3,8,56B）3,29,8,56,35,11,20,74C）3,8,11,20,29,35,56,74D）20,29,3,8,11,35,74,569.下列关键码序列中，属于堆的是（A）。A)（15，30，22，93，52，71） B)（15，7
7、1，30，22，93，52）C)（15，52，22，93，30，71）D)（93，30，52，22，15，71）10.若要求尽可能快地对实数数组进行稳定的排序，则应选(C)。A)快速排序 B)堆排序 C)归并排序 D)基数排序11.下列排序算法的时间复杂度最小的是（D）。A)冒泡排序 B)希尔排序C)简单选择排序 D)归并排序12.设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好（ C）排序法。A)起泡排序 B)快速排序 C)堆排序 D)基数排序13.插入排序算法在每一趟都能选取出一个元素放在其最终的位置上。( B )A)正确 B)不正确14.直接插入排序是不稳定的
8、排序方法。( B )A)正确 B)不正确15.直接插入排序的最坏情况是初始序列为（ B ）序。A)正 B)反 C)正和反 D)无16.在各排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为(D )。A)希尔排序 B)归并排序 C)插入排序 D)选择排序栈和队列1.栈的特点是( B )。A）先进先出 B）后进先出C）进优于出 D）出优于进2.栈和队列都是（C）。 A）顺序存储的线性结构 B）链式存储的线性结构C）操作受限的线性结构 D）操作受限的非线性结构3.链栈与顺序栈相比，有一个比较明显的优点是（B）。A）插入操作更加方便 B）通常不会出现栈满的情况
9、C）不会出现栈满的情况 D）删除操作更加方便4.一个栈的入栈序列是a,b,c,d, 则下列序列中不可能的输出序列是（ D ）。A）acbd B）dcbaC）acdb D）dbac5.设有一空栈,现有输入序列为1,2,3,4,5,经过PUSH,PUSH，POP，PUSH，POP，PUSH，PUSH后，输出序列为（C ）。A）5,4,3,2,1 B）2,1 C）2,3 D）2,4 6.下面哪种数据结构不适合作栈的存储结构（D ）。A）数组 B）单链表 C）静态链表 D）二叉树结构7.设计一个判别表达式中左右括号是否配对出现的算法，最好采用（C ）结构。A）线性表 B）队列 C）堆栈 D）树8.队列
10、的操作原则是( A ) 。A）先进先出 B）先进后出C）只能进行插入 D）只能进行删除 9. 判断一个循环队列是空队列的条件是（A ）。 A）Q.rear = Q.front B）Q.front = 0C）Q.rear = 0 10.在具有n个单元顺序存储的循环队列中，队满时共有（B ）个元素。A）n+1 B）n-1 C）n D）n+211.若一个栈的输入序列是1,2,3,n,输出序列的第一个元素是n,则第i个输出元素是( B )。A) n-i B) n-i+1 C) i D) 不确定 12.判断当字符序列 x5y 作为字符堆栈的输入时，输出长度为3的且可以作为C语言标识符的个数是（ A ）。
11、A) 3个 B) 4个 C) 5个 D) 6个 13.采用不带尾指针的单链表方式表示一个栈，便于结点的插入与删除。栈顶结点的插入与删除通常在链表的（C）进行。A)任意位置 B)链表头尾两端C)链表头一端 D)链表尾一端14.在一个链队列中,若Q.front、Q.rear分别为队首、队尾指针，则插入s所指结点的操作为（ B ）。A) Q.front-next=s; Q.front=s; B) Q.rear-next=s; Q.rear=s;C) s-next=Q.front; Q.rear=s;D) s-next=Q.front; Q.front=s;串和数组1.串是一种特殊的线性表，其特殊性体
12、现在( C ) 。 A)可以顺序存储 B)可以用链表存储 C)数据元素是一个字符 D)数据元素可以是多个字符2.串是（ D ）。 A）少于一个字母的序列 B）任意个字母的序列C）不少于一个字符的序列 D）有限个字符的序列3.串的长度是（ D ）。A）串中不同字母的个数 B）串中不同字符的个数C）串中所含字符的个数，且大于0D）串中所含字符的个数4.设有两个串p和q,求q在p中首次出现的位置的运算(B ). A）连接 B）模式匹配C）求子串 D）求串长5.若某串的长度小于一个常数，则采用( C )存储方式最为节省空间。A)链式 B)堆结构 C)顺序6.串中任意多个连续字符组成的子序列称为该串的子串(A ).A)正确 B)不正确7.如果两个串含有相同的字符集，则说两者相等( B ). A)正确 B)不正确8.存取数组中任一元素的时间都是相等的，这种存取方式为（ B）存取方式。A）顺序 B）随机 C）线性 D）非线性 9.设一个一维数组第一个元素的存储单元的地址是100，每个元素的长度是6，则它的第5个元素的地址是（D ）。A）130 B）105 C）106 D）12410.设n阶方阵是一个上三角矩阵，则需要存储的元素个数是（B）。A）n2/2 B）n(n+1)/2 C）n D）n211.对一些特殊矩阵采用压缩存储的目的主要是为（B ）。A）表达变得简单 B）减少不必要
