数据结构选择题Word版

第八章排序：习题习题一、选择题1．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。

A.希尔排序B.冒泡排序C.插入排序D.选择排序2．设有1000个无序的记录，希望用最快的速度挑选出其中前10个最大的记录，最好选用( )排序法。

A.冒泡排序B.快速排序C.堆排序D.基数排序3．在待排序的记录序列基本有序的前提下，效率最高的排序方法是( )。

A.插入排序B.选择排序C.快速排序D.归并排序’4．不稳定的排序方法是指在排序中，关键字值相等的不同记录的前后相对位置( )。

A.保持不变B.保持相反C.不定D.无关5．内部排序是指在排序的整个过程中，全部数据都在计算机的( )中完成的排序。

A. 内存储器B.外存储器C.内存储器和外存储器D.寄存器6．用冒泡排序的方法对n个数据进行排序，第一趟共比较( )对记录。

A.1B.2C.n-lD.n7．直接插入排序的方法是从第( )个记录开始，插入前边适当位置的排序方法。

A.1B.2C.3D.n8．用堆排序的方法对n个数据进行排序，首先将n个记录分成( )组。

A.1B.2C.n-lD.n9．归并排序的方法对n个数据进行排序，首先将n个记录分成( )组，两两归并。

A.1B.2C.n-lD.n10．直接插入排序的方法要求被排序的数据( )存储。

A.必须是顺序B.必须是链表C.顺序或链表D.二叉树11．冒泡排序的方法要求被排序的数据( )存储。

A.必须是顺序B.必须是链表C.顺序或链表D.二叉树12．快速排序的方法要求被排序的数据( )存储。

A.必须是顺序B.必须是链表C.顺序或链表D.二叉树13．排序方法中，从未排序序列中依次取出记录与已排序序列（初始时为空）中的记录进行比较，将其放入已排序序列的正确位置上的方法，称为( )。

A.希尔排序B.冒泡排序C.插入排序D.选择排序14．每次把待排序的记录划分为左、右两个子序列，其中左序列中记录的关键字均小于等于基准记录的关键字，右序列中记录的关键字均大于基准记录的关键字，则此排序方法叫做( )。

单元练习2一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（×）（1）线性表的链式存储结构优于顺序存储。

（×）（2）链表的每个结点都恰好包含一个指针域。

（√）（3）在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

（×）（4）顺序存储方式的优点是存储密度大，插入、删除效率高。

（×）（5）线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

（×）（6）顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

（√）（7）线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。

（√）（8）线性表采用顺序存储，必须占用一片连续的存储单元。

（×）（9）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

（ㄨ）（10）插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。

二．填空题（1）顺序表中逻辑上相邻的元素在物理位置上必须相连。

（2）线性表中结点的集合是有限的，结点间的关系是一对一关系。

（3）顺序表相对于链表的优点是：节省存储和随机存取。

（4）链表相对于顺序表的优点是：插入、删除方便。

（5）采用顺序存储结构的线性表叫顺序表。

（6）顺序表中访问任意一个结点的时间复杂度均为O(1)。

（7）链表相对于顺序表的优点是插入、删除方便；缺点是存储密度小。

（8）在双链表中要删除已知结点*P，其时间复杂度为O(1)。

（9）在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为 O(n) 。

（10）单链表中需知道头指针才能遍历整个链表。

（11）线性表中第一个结点没有直接前趋，称为开始结点。

（12）在一个长度为n的顺序表中删除第i个元素，要移动n-i 个元素。

（13）在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移n- i +1 个元素。

数据结构－树练习题一、选择题1、二叉树的深度为k，则二叉树最多有（ C ）个结点。

A. 2kB. 2k-1C. 2k-1D. 2k-12、用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（ B ）。

A. R[2i-1]B. R[2i+1]C. R[2i]D. R[2/i]3、设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（ B ）。

A. a在b的右方B. a在b的左方C. a是b的祖先D. a是b的子孙4、设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（）。

A. adbceB. decabC. debacD. abcde5、在一棵具有5层的满二叉树中结点总数为（ A ）。

A. 31B. 32C. 33D. 166、由二叉树的前序和后序遍历序列（ B ）惟一确定这棵二叉树。

A. 能B. 不能7、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（C ）。

A. 3B. 2C. 4D. 58、若以{4,5,6,7,8}作为权值构造哈夫曼树，则该树的带权路径长度为（C ）。

A. 67B. 68C. 69D. 709、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（A ）。

A. 98B. 99C. 50D. 4810、表达式a*(b+c)-d的后缀表达式是（ B ）。

A. abcd+-B. abc+*d-C. abc*+d-D. -+*abcd11、对某二叉树进行先序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果是（ B ）。

A. DBFEACB. DFEBCAC. BDFECAD. BDEFAC12、树最适合用来表示（ C ）。

要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。

每张答题纸都要写上姓名和学号。

一、单项选择题(每小题2分，共20小题，共计40分)1.某算法的空间复杂度为0(1),则。

A.该算法执行不需要任何辅助空间B.该算法执行所需辅助空间大小与问题规模n无关C.该算法执行不需要任何空间D.该算法执行所需全部空间大小与问题规模n无关2.在长度为n的顺序表中插入一个元素，对应算法的时间复杂度为。

A.0(1)B.O(log2n)C.0(n)D.0(n2)3.设线性表中有n个元素，以下运算中，在单链表上实现要比在顺序表上实现效率更高。

A.删除指定位置元素的后一个元素B.在最后一个元素的后面插入一个新元素C.顺序输出前k个元素D.交换第i个元素和第n-i+1个元素的值(i=1, 2,…，n)4.以下数据结构中元素之间为非线性关系的是。

A.栈B.队列C.线性表D.以上都不是5.若一个栈用数组data[1..n]存储，初始栈顶指针top为n+1,则以下元素x进栈的正确操作是。

A.top++;data[top]=x;B.data[top]=x;top++;C.top-- ;data[top]=x;D.data[top]=x;top --;6.若某循环队列有队首指针front和队尾指针rear,在队不满时进队操作仅会改变。

A.frontB.rearC.front 和rearD.以上都不队7.设循环队列中数组的下标是0〜N-1,其队头、队尾指针分别为f和r(f指向队首元素的前一位置，r指向队尾元素)，则其元素个数为。

A.r-fB.r-f-1C.(r-f)%N+1D.(r-f+N)%N8.设树T的度为4,其中度为1、2、3、4的结点个数分别为4、2、1、1,则T中的叶子结点个数是。

A.5B.6C.7D.89. 一棵哈夫曼树中共有199个结点，它用于多少个字符的编码。

A.99B.100C.101D.19910.设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为a、b、c、d,将森林F转换为一颗二叉树B,则二叉树B根结点的左子树上的结点个数是。

模拟试题四模拟试题四一、选择题（20分）1。

由两个栈共享一个存储空间的好处是（)。

A）减少存取时间，降低下溢发生的几率B）节省存储空间，降低上溢发生的几率C)减少存取时间，降低上溢发生的几率D)节省存储空间,降低下溢发生的几率2。

设有两个串p和q，求q在p中首次出现位置的运算称做（)。

A）连接B）模式匹配 C）求子串D)求串长3。

n个顶点的连通图中边的条数至少为（)。

A)0 B）l C）n—l D）n4.对一个具有n个元素的线性表,建立其有序单链表的时间复杂度为( ）。

A)O(n）B）O(1）C）O（n2） D) O(log2n）5.在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是( ）。

A) p—>next=s; s—〉prior=n；p->next—>prior=s；s-〉next:p->next。

B) s—〉priOFp；s->next—p->next；p—>next=s; p—〉next->priOFS.C) p-〉next=s；p-〉next—〉priOFS; s->prior=p; s-〉next=p—〉next.D) s—>prior=p; s-〉next=p—〉next; p-〉next—〉priOFS；p-〉next=S.6，串的长度是( ）.A）串中不同字符的个数 B)串中不同字母的个数C)串中所含字符的个数n（n>0) D)串中所含字符的个数n（n≥0)7.若有一个钱的输入序列是l,2,…,n，输出序列的第一个元素是n，则第i个输出元素是（）。

A) n—i B) n—i—l C）n—i+l D）不确定8.设有一个栈，元素的进栈次序为A，B，C，D，E，下列( )是不可能的出栈序列。

A) A，B，C,D，E B）B，C, D，E,AC）E，A, B，C,D D)E，D, C，B,A9。

在一棵度为3的树中,度为3的结点数有2个，度为2的结点数有1个，度为l的结点数有2个，那么度为0的结点数有（)个。

注意事项：1、下面关于串的叙述中，哪一个是不正确的？（ ）A ．串是字符的有限序列B ．空串是由空格构成的串C ．模式匹配是串的一种重要运算D ．串既可以采用顺序存储，也可以采用链式存储 2、设无向图的顶点个数为n ，则该图最多有（ ）条边。

A ．n-1B ．n(n-1)/2C ． n(n+1)/2D ．0 3、以下数据结构中，（ ）是非线性数据结构。

A ．树B ．字符串C ．队列D ．栈 4、下面关于线性表的叙述中，错误的是哪一个？（ ）A ．线性表采用顺序存储，必须占用一片连续的存储单元。

B ．线性表采用顺序存储，便于进行插入和删除操作。

C ．线性表采用链接存储，不必占用一片连续的存储单元。

D ．线性表采用链接存储，便于插入和删除操作。

5、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front 和rear ，则当前队列中的元素个数为（ ）。

A ．(rear-front+m)%mB ．rear-front+1C ．(front-rear+m)%mD ．(rear-front)%m6、在单链表指针为p 的结点之后插入指针为s 的结点,正确的操作是（ ）。

A ．p->next=s; s->next=p->next;B ．s->next=p->next; p->next=s;C ．p->next=s; p->next=s->next;D ．p->next=s->next; p->next=s; 7、设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。

A ．1，2，4，3B ．2，1，3，4C ．1，4，3，2D ．4，3，1，2， 8、广义表（a,(b,c),d,e ）的表头和表尾分别为（ ）。

A ．a 和(b,c),d,e B ．（a ）和(b,c),d,eC ．a 和 ((b,c)，d,e)D ．(a) 和((b,c)，d,e)9、栈和队都是（ ）A ．顺序存储的线性结构B ．链式存储的非线性结构C ．限制存取点的线性结构D ．限制存取点的非线性结构 10、从逻辑上可以把数据结构分为（ ）两大类。

“数据结构”期末考试试题一、单选题(每小题2分，共12分)1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。

A． HL＝ps p一>next＝HLB． p一>next＝HL；HL＝p3C． p一>next＝Hl；p＝HL；D． p一>next＝HL一>next;HL一>next＝p；2．n个顶点的强连通图中至少含有( )。

A.n—l条有向边B.n条有向边C.n(n—1)／2条有向边D.n(n一1)条有向边3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。

A.O(1)B.O(n)C.O(1Ogzn)D.O(n2)4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。

A．24 B．48C． 72 D． 535．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。

A.整形B.引用型C.指针型D.常值引用型·6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。

A．O(n) B．O(1)C．O(n2) D．O(10g2n)二、填空题(每空1分，共28分)1．数据的存储结构被分为——、——、——和——四种。

2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。

3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。

4．在一棵高度为h的3叉树中，最多含有——结点。

5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。

7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。

第一章习题判断题1．数据元素是数据的最小单位。

( )2．记录是数据处理的最小单位。

( )3．数据的逻辑结构是指数据的各数据项之间的逻辑关系。

( )4．算法的优劣与算法描述语言无关，但与所用计算机有关。

( )5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。

( )6．算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。

( )7．程序一定是算法。

( )8．数据的物理结构是指数据在计算机内的实际存储形式。

( )9．数据结构的抽象操作的定义与具体实现有关。

( )10．在顺序存储结构中，有时也存储数据结构中元素之间的关系。

( )11．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

( )12．数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。

( )13．数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。

( )答案1．× 2．× 3．× 4．× 5．√6．× 7．× 8．√ 9．× 10．×11．× 12．√ 13．×填空题1．数据的物理结构包括____ 的表示和____ 的表示。

2．对于给定的n个元素,可以构造出的逻辑结构有（1），（2），（3），（4）四种。

3．数据的逻辑结构是指_____。

4．一个数据结构在计算机中______称为存储结构。

5．抽象数据类型的定义仅取决于它的一组（1），而与（2）无关，即不论其内部结构如何变化，只要它的（3）不变，都不影响其外部使用。

6．数据结构中评价算法的两个重要指标是_______。

7．数据结构是研讨数据的（1）和（2），以及它们之间的相互关系，并对与这种结构定义相应的（3），设计出相应的（4）。

8．一个算法具有5个特性: （1）、（2）、（3），有零个或多个输入、有一个或多个输出。

第九章查找：习题习题一、选择题1．散列表查找中k个关键字具有同一散列值，若用线性探测法将这k个关键字对应的记录存入散列表中，至少要进行( )次探测。

A. k B。

k+l C. k(k+l）／2 D. l+k （k+l)/22．下述命题( )是不成立的。

A。

m阶B-树中的每一个结点的子树个数都小于或等于mB。

m阶B-树中的每一个结点的子树个数都大于或等于『m/2-1C。

m阶B-树中的每一个结点的子树高度都相等D。

m阶B—树具有k个子树的非叶子结点含有(k-l）个关键字3．如果要求一个基本线性表既能较快地查找，又能适应动态变化的要求，可以采用( ）查找方法.A。

分块 B. 顺序 C. 二分 D.散列4．设有100个元素，用折半查找法进行查找时，最大比较次数是( ),最小比较次数是( ）.A。

7，1 B.6，l C.5，1 D. 8，15．散列表长m=15，散列表函数H(key）=key％13。

表中已有4个结点：addr（18)=5；addr(32）=6; addr(59)=7；addr(73)=8;其余地址为空，如果用二次探测再散列处理冲突，关键字为109的结点的地址是( )。

A. 8 B。

3 C. 5 D。

46．用分块查找时，若线性表中共有729个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分( )个结点最佳。

A。

15 B. 27 C。

25 D。

307．散列函数有一个共同性质，即函数值应当以( )取其值域的每个值。

A.同等概率B。

最大概率C。

最小概率D。

平均概率8．设散列地址空间为O.。

m—1，k为关键字，假定散列函数为h(k)=k％p，为了减少冲突，一般应取p为( )。

A.小于m的最大奇数B. 小于m的最大素数C.小于m的最大偶数D.小于m的最大合数9．当向一棵m阶的B-树做插入操作时，若使一个结点中的关键字个数等于( )，则必须分裂成两个结点。

A。

m B。

m-l C.m+l D。

第7章图一、选择题（每小题1分，共10分）1.一个n个顶点的连通无向图，其边的个数至少为（ C ）。

A.n+lB.nC.n-lD.2n2.下列哪一种图的邻接矩阵是对称矩阵（ B ）。

A.有向图B.无向图C.AOV网D.AOE网3.为解决计算机和打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是（ B ）。

A.栈B.队列C.树D.图4.设无向图的顶点个数为n，则该图最多有（ C ）条边。

A. n-1B. n(n-1)/2C. n(n+1)/2D. 2n5.无向图G=(V,E),其中：V={a,b,c,d,e,f}, E={(a,b),(a,e),(a,c),(b,e),(c,f), (f,d),(e,d)}，由顶点a开始对该图进行深度优先遍历，得到的顶点序列正确的是（ D ）。

A. a,b,e,c,d,fB. a,c,f,e,b,dC. a,e,b,c,f,dD. a,e,d,f,c,b6.用邻接表表示图进行广度优先遍历时，通常是采用（ B ）来实现算法的。

A.栈B.队列C.树D.图7.以下数据结构中，哪一个是线性结构（ D ）。

A.广义表B.二叉树C.图D.栈8.下面哪一方法可以判断出一个有向图是否有环（回路）（ B ）。

A.最小生成树B.拓扑排序C.求最短路径D.求关键路径9.在一个图中，所有顶点的度数之和等于图的边数的（ C ）倍。

A. 1/2B. 1C. 2D. 410.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。

A. 1/2B. 1C. 2D. 411.有8个顶点无向图最多有（ B ）条边。

A. 14B. 28C. 56D. 11212.有8个顶点无向连通图最少有（ C ）条边。

A. 5B. 6C. 7D. 813.有8个顶点有向完全图有（ C ）条边。

A. 14B. 28C. 56D. 11214.下列说法不正确的是（ A ）。

数据结构考试题及答案一、选择题1. 以下哪种数据结构在实现栈时最为高效？A. 链表B. 数组C. 树D. 图答案：B2. 快速排序算法的时间复杂度在最坏情况下是多少？A. O(n)B. O(nlogn)C. O(n^2)D. O(n^3)答案：C3. 在二叉搜索树中，若要查找给定值的节点，应该按照以下哪种方式进行？A. 从根节点开始，向左或向右子树交替进行B. 从根节点开始，始终向左子树进行C. 从根节点开始，始终向右子树进行D. 从最底层节点开始向上进行答案：A4. 哈希表的主要优点是什么？A. 有序存储数据B. 高效的查找、插入和删除操作C. 动态扩容D. 消耗内存小答案：B5. 下面哪种数据结构通常用于实现高效的多对一映射？A. 数组B. 链表C. 哈希表D. 树答案：C二、填空题1. 在平衡树中，AVL树通过_________来保持树的平衡。

答案：旋转2. 堆数据结构通常用来实现_________等优先队列。

答案：最大/最小3. 拓扑排序是针对有向无环图(DAG)的一种排序算法，它能够反映出任务间的_________关系。

答案：依赖4. 广度优先搜索(BFS)算法使用_________数据结构来实现。

答案：队列5. 斐波那契数列可以通过递归算法、动态规划以及_________等方法来计算。

答案：矩阵快速幂三、简答题1. 请简述链表和数组的区别及各自的优缺点。

答案：链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

它的优点是能够在常数时间内在任意位置插入或删除元素，但随机访问效率较低。

数组是一段连续的内存空间，可以存储一系列相同类型的元素。

它的优点是支持高效的随机访问，但插入和删除操作通常需要移动大量元素，且大小固定或调整大小成本较高。

2. 描述二分查找的工作原理及其适用条件。

答案：二分查找是一种在有序数组中查找特定元素的算法。

它的工作原理是将数组分为两半，比较中间元素与目标值，如果相等则查找结束；如果目标值较小，则在左半部分继续查找；如果目标值较大，则在右半部分继续查找。

mulchoose0@*@3mulchoose0@*@1@*@2 1 . 以下说法正确的是（)A . 二叉树的特点是每个结点至多只有两棵子树。

B . 二叉树的子树无左右之分。

C . 二叉树只能进行链式存储。

D . 树的结点包含一个数据元素及若干指向其子树的分支。

答案：A ，D解析：2 . 算法设计的要求包括 。

A . 正确性B . 可读性C . 健壮性D . 确定性答案：A ，B ，C解析： “确定性”属于算法特性而非要求。

3 . 下列属于算法的重要特征的是：A . 有穷性B . 确定性C . 可行性D . 输入和输出答案：A ，B ，C ，Dmulchoose0@*@1@*@2@*@3 mulchoose0@*@1@*@2@*@3mulchoose0@*@3解析： ABCD4 . 图的四中存储结构A . 邻接矩阵B . 邻接表C . 邻接多重表D . 十字链表答案：A ，B ，C ，D解析：5 . 依据所有数据成员之间的逻辑关系的不同，数据结构分为（）A . 非线性结构B . 逻辑结构C . 物理结构D . 线性结构答案：A ，D解析：6 . 图的应用算法有（）A . 克鲁斯卡尔算法B . 哈弗曼算法mulchoose0@*@2@*@3C . 迪杰斯特拉算法D . 拓扑排序算法答案：A ，C ，D解析：7 . 计算机算法必须具备等特性。

A . 可行性、确定性B . 可行性、可移植性C . 输入、输出D . 有穷性E . 易读性F . 稳定性答案：A ，C ，D解析：0@*@2@*@3mulchoose8 . 下列数据结构中，属于线性数据结构的是A . 栈B . 队列C . 树D . 图答案：A ，Bmulchoose0@*@1mulchoose1@*@2@*@4mulchoose0@*@2解析：9 . 下列说法正确的有：A . 算法和程序原则上没有区别，在讨论数据结构时二者通用B . 从逻辑关系上讲，数据结构分为两大类：线性结构和非线性结构C . 所谓数据的逻辑结构是指数据元素之间的逻辑关系D . 同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数相等E . 数据的逻辑结构与数据元素本身的内容和形式无关F . 数据结构是指相互之间存在一种或多种关系的数据元素的全体答案：B ，C ，E解析：10 . 线性表的特点正确的（）A . 存在唯一的一个被称作”第一个“的数据元素。

数据结构试卷（一）王彬一、单选题（每题2 分，共20分）1.栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

cA．688 B．678 C．692 D．6965.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( d ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ c d）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：____ ____、________、________和_______。

2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

1、在以下哪种数据结构中，元素的存储顺序与其逻辑顺序不一致？A. 顺序表B. 单链表C. 双链表D. 栈（答案：B）2、下列哪个数据结构最适合用于实现优先级队列？A. 哈希表B. 二叉搜索树C. 二叉堆D. 双向链表（答案：C）3、对于一个频繁进行插入和删除操作，且要求快速查找的动态集合，最适合使用哪种数据结构？A. 数组B. 链表C. 平衡二叉搜索树D. 直接寻址表（答案：C）4、在图数据结构中，用来表示顶点之间关系的是？A. 边B. 节点C. 权重D. 路径（答案：A）5、下列哪项不是树结构的一种？A. 二叉树B. AVL树C. B树D. 队列（答案：D）6、在深度优先搜索（DFS）中，使用哪种数据结构来跟踪待访问的节点？A. 栈B. 队列C. 散列表D. 优先队列（答案：A）7、下列关于哈希表的说法中，错误的是？A. 哈希表能够提供快速的查找、插入和删除操作B. 哈希函数的选择对哈希表的性能至关重要C. 链地址法解决哈希冲突时不会产生同义词D. 哈希表的平均查找时间复杂度可以是O(1)（答案：C）8、在二叉树的前序遍历中，节点的访问顺序是？A. 根节点 -> 左子树 -> 右子树B. 左子树 -> 根节点 -> 右子树C. 右子树 -> 根节点 -> 左子树D. 左子树 -> 右子树 -> 根节点（答案：A）9、下列哪种数据结构最适合用于实现撤销（undo）操作？A. 栈B. 队列C. 哈希表D. 二叉树（答案：A）10、在并查集数据结构中，用于合并两个集合的操作是？A. FindB. UnionC. MakeSetD. PathCompression（答案：B）。

第1章绪论5．选择题：CCBDCA6．试分析下面各程序段的时间复杂度。

（1)O（1）（2）O(m＊n）（3）O（n2）（4)O（log3n）（5)因为x++共执行了n—1+n—2+……＋1= n(n—1)/2，所以执行时间为O(n2)（6）O(n）第2章线性表1．选择题babadbcabdcddac2．算法设计题(6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

ElemType Max （LinkList L ）｛if(L—〉next==NULL) return NULL；pmax=L-〉next；//假定第一个结点中数据具有最大值p=L-〉next—>next；while(p ！= NULL ){//如果下一个结点存在if（p->data > pmax—>data) pmax=p；p=p->next；｝return pmax-〉data;（7)设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间.void inverse(LinkList ＆L) ｛// 逆置带头结点的单链表Lp=L-〉next；L->next=NULL；while （p）｛q=p—>next；// q指向＊p的后继p->next=L—>next;L—>next=p; // *p插入在头结点之后p = q;｝}（10)已知长度为n的线性表A采用顺序存储结构,请写一时间复杂度为O(n)、空间复杂度为O（1）的算法，该算法删除线性表中所有值为item的数据元素.［题目分析］在顺序存储的线性表上删除元素,通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n个元素要依次前移)。

本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。

因此可以考虑设头尾两个指针（i=1，j=n）,从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。

（完整版）数据结构试题及答案《数据结构》自考复习思考试题○10一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合C. 类型的有限集合D. 关系的有限集合2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( )A. n-i+1B. iC. i+1D. n-i3. 若不带头结点的单链表的头指针为head，则该链表为空的判定条件是( )A. head==NULLB. head->next==NULLC. head!=NULLD. head->next==head4. 引起循环队列队头位置发生变化的操作是( )A. 出队B. 入队C. 取队头元素D. 取队尾元素5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( )A. 2，4，3，1，5，6B. 3，2，4，1，6，5C. 4，3，2，1，5，6D. 2，3，5，1，6，46. 字符串通常采用的两种存储方式是( )A. 散列存储和索引存储B. 索引存储和链式存储C. 顺序存储和链式存储D. 散列存储和顺序存储7. 设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为( )A. mB. n-mC. n-m+1D. n8. 二维数组A［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A［9］［7］的地址为( )A. 429B. 432.C. 435D. 4389. 对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是( )A. (e,f)B. ((e,f))C. (f)D. ( )10. 下列图示的顺序存储结构表示的二叉树是( )11. n个顶点的强连通图中至少含有( )A. n-1条有向边B. n条有向边C. n(n-1)/2条有向边D. n(n-1)条有向边12. 对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为( )A. (19，23，56，34，78，67，88，92)B. (23，56，78，66，88，92，19，34)C. (19，23，34，56，67，78，88，92)D. (19，23，67，56，34，78，92，88)13. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为( ) A. 4 B. 5C. 8D. 914. 由同一关键字集合构造的各棵二叉排序树( )A. 其形态不一定相同，但平均查找长度相同B. 其形态不一定相同，平均查找长度也不一定相同C. 其形态均相同，但平均查找长度不一定相同.D. 其形态均相同，平均查找长度也都相同15. ISAM文件和VSAM文件的区别之一是( )A. 前者是索引顺序文件，后者是索引非顺序文件B. 前者只能进行顺序存取，后者只能进行随机存取C. 前者建立静态索引结构，后者建立动态索引结构D. 前者的存储介质是磁盘，后者的存储介质不是磁盘二、填空题(本大题共10小题，每空2分，共20分)16. 数据的逻辑结构在计算机存储器内的表示，称为数据的____________。

模拟试题二模拟试题二一、选择题（28分）1.设一数列的顺序为l，2，3,4，5,通过栈结构不可能排成的顺序数列为( )。

A)3,2，5，4，l B)1，5,4，2，3C）2，4，3,5,l D）4，5，3，2,l2。

二叉树的第3层最少有（)个结点。

A)0 B）1 C)2 D）33。

—个n个顶点的连通无向图，其边的个数至少为( )。

A) n-l B)n C）n+l D）nlogn4。

下列排序方法中，( ）的比较次数与记录的初始排列状态无关。

A）直接插入排序 B）起泡排序C）快速排序 D）直接选择排序5.-棵哈夫曼树总共有II个结点，则叶子结点有( ）个。

A）5 B）6 C）7 D)96.已知某算法的执行时间为（n+n2)+log2(n+2)，n为问题规模,则该算法的时间复杂度是( ）。

A)O（n）B）O（n2) C）O（log2n）D）O(nlog2n)7。

如果一棵树有10个叶子结点，则该树总共至少有( )个结点。

A）lO B）11 C）19 D) 218。

—个100×100的三角矩阵a采用行优先压缩存储后，如果首元素a[0]［0]是第一个元素，那么a[4] [2］是第( )个元素。

A）13 B) 401 C) 402 D）4039.有一棵二叉树如题图1,该树是（）。

A）二叉平衡树B)二叉排序树C)堆的形状D)以上都不是10。

对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树，其时间复杂度为（)，利用Kruska算法的时间复杂度为（).A）O（log2n) B）0(n2) C)O（ne) D）O（elog2ne)11.具有n个顶点的完全有向图的边数为( ）.A）n（n—l)/2 B）n（n-l） C) n2 D）n2—112。

设有100个元素，用折半查找时,最大比较次数为（)，最小比较次数为（）。

A）25 B)7 C) 10 D)l13。

在内部排序中，排序时不稳定的有（).A）插入排序B）冒泡排序C）快速排序D）归并排序14.串是一种特殊的线性表，其特殊性体现在（)。