E__Temp2_2013数据结构试题

E__Temp2_2013数据结构试题

2013数据结构试卷

一、选择题(每空题2分共30分)

1．下列关于算法的说法，正确的是（）。

A．程序一定是算法。

B．算法的可行性是指指令不能有二义性。

C．算法可以没有输入但必须有1个以上的输出。

D．算法必须是用计算机语言描述的。

2．从一个具有n个结点的单链表中查找值为x结点，在查找成功情况下，需平均比较（）个结点。

A． n B． n/2 C． (n-1)/2 D． (n+1)/2

3．带头结点的单链表head为空的判定条件是( )。

A． head= =NULL B． head->next==NULL

C． head->next= =head D． head!=NULL

4. 循环队列存储在数组A[0..m]中，则入队时的操作为（）。

A. rear=rear+1

B. rear=(rear+1) mod (m-1)

C. rear=(rear+1)mod m

D. rear=(rear+1)mod(m+1)

5. 广义表L=((a,b,c))的长度和深度分别是（）。

A.1和1

B.1和3

C.1和2

D.2和3

6．广义表运算式Tail(((a,b),(c,d)))的操作结果是（）。。A．（c,d） B．c,d C．((c,d)) D．（）

7．表达式a*(b+c)-d的后缀表达式是（）。。

A．abcd*+- B．abc+*d- C．abc*+d- D．-+*abcd

8．设n阶方阵A是一对称矩阵，为节省存储空间，将其下三角

（包括对角线）以行序为主序存储在一维数组B(1: n(n+1)/2)中，则对任一上三角元素aij(i

A．i(i-1)/2+j B．j(j-1)/2+i C．i(j-1)/2+1 D．j(i-1)/2+1

9．广义表((a))的表头是（）。。

A．a B．(a) C．() D．((a))

10.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

A）单链表 B）仅有头指针的单循环链表

C）双链表 D）仅有尾指针的单循环链表

11. 在数据结构中，从逻辑上可以把数据结构分成（）。

A）动态结构和静态结构 B）紧凑结构和非紧凑结构

C）线性结构和非线性结构 D）内部结构和外部结构

12. 在一个不带头结点单链表H中，若要向表头插入一个由指针p 指向的结点，则执行（）。

A. H=p; p->next=H;

B. p->next=H; H=p;

C. p->next=H; p=H;

D. p->next=H->next; H->next=p;

13. 栈的插入和删除操作在（）进行。

A. 栈顶

B. 栈底

C. 任意位置

D. 指定位置

14. 从顺序串中删除一个字符的时间复杂度为( )。

A．O(1) B. O(n) C.O(1og

2n) D. O(nlog

2

n)

15. 以下说法正确的是( )。

A. 数据元素是数据的最小单位

B. 数据项是数据的基本单位

C. 原子类型不可再分解

D. 数据项只能是原子类型

二、填空题(每空1分共14分)

1．当对一个线性表经常进行的是插入和删除操作时，采用存储结构为

宜,当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最

好采用存储结构。

2．下面程序段的时间复杂度是。

i ＝ 0；

while（i<=n）

i = i * 3；。

3.如果一个过程直接或间接地调用自己，则称这个过程是一个过程。

4．广义表L=(a,(b,c)),可用head()和tail()分别求广义表的头和尾，则c= ___________。

5. 用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到

1342出栈顺序，相应的S和X的操作串为。

6．循环队列的引入，目的是为了克服

7．二维数组A[6][8]采用行序为主方式存储，每个元素占4个存储单元，已知

A的起始存储地址(基地址)是1000，则A[2][3]的地址是

8. 广义表(a,(a,b),d,e,((i,j),k))的长度是，深度是。

9. 在一个长度为n的顺序存储结构的线性表中，向第i个元素(1≤i≤n+1)之前

插入一个新元素时，需向后移动个元素

10. 设有两个串p和q，求q在p中首次出现的位置的运算称为

11．评估一个算法的优劣，通常从和两个方面考察

12．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快

的速度存取线性表的元素是，应采用存储结构。

三、判断题（10分）

1、抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定

义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。( )

2、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（）

3、在决定选取何种存储结构时，一般不考虑各结点的值如何。（）

4、对任何数据结构链式存储结构一定优于顺序存储结构。（）

5、循环链表不是线性表。（）

6、队列是一种插入和删除操作分别在表的两端进行的线性表，是一种先进后出

的结构。（）

7、数组元素的下标值越大，存取时间越长。( )

8、一个广义表的表头总是一个广义表。（）

9、串是一种特殊的线性表，其特殊性体现在可以顺序存储。（）

10、在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：p->next = s; s->next = p->next; ( )

四、分析应用题（每个问题2分，第四题5分计25分）

1、已知head为带头结点的单循环链表的头指针，链表中的数据元素依次为（a

1

，

a 2,a

3

,a

4

,…,a

n

）,A为指向空的顺序表的指针。阅读以下程序段，并回答问题：（1）写出执行下列程序段后的顺序表A中的数据元素；

（2）简要叙述该程序段的功能。

if(head->next!=head)

{

p=head->next;

A->length=0;

while(p->next!=head)

{

p=p->next;

A->data[A->length ++]=p->data;

if(p->next!=head)p=p->next;

}

}

(1)

(2)

2．已知链串的存储结构描述如下：

#define NodeSize 4

typedef struct Node {

char data [NodeSize];

struct Node * next;

} * LinkStr;

阅读下列算法，并回答问题：

（1）t1和t2的串值分别为″Chinese″和″China″时，写出f31(t1,t2)的返回值；

（2）t1和t2的串值分别为″Japan″和″Japanese″时，写出f31(t1,t2)的返回值；

（3）t1和t2的串值都为″string″时，写出f31(t1,t2)的返回值；

（4）简述函数f31的功能。

inf f31(LinkStr t1,LinkStr t2)

{//串值以′\0′为结束符

int i;

while (1){

for (i=0;i

if (t1->data[i]= =′\0′&&t2->data[i]= =′\0′return 0;

if(t1->data[i]= =′\0′))return –1;

if(t2->data[i]= =′\0′))return 1;

if(t1->data[i]>t2->data[i]return 1;

if(t1->data[i]data[i]return –1;

}

t1=t1->next;

t2=t2->next;

}

}

(1)

(2)

(3)

(4)

3．已知用有序链表存储整数集合的元素。阅读算法f30，并回答下列问题：（1）写出执行f30（a,b）的返回值，其中a和b分别为指向存储集合{2，4，5，7，9，12}和{2，4，5，7，9}的链表的头指针；

（2）简述算法f30的功能；

（3）写出算法f30的时间复杂度。

int f30(LinkList ha,LinkList hb)

{

//LinkList是带有头结点的单链表

//ha和hb分别为指向存储两个有序整数集合的链表的头指针

LinkList pa,pb;

pa=ha->next;

pb=hb->next;

while(pa && pb && pa->data==pb->data)

{ pa=pa->next;

pb=pb->next;

}

if(pa==NULL && pb==NULL) return 1;

else return 0;

}

(1)

(2)

(3)

4、已知广义表L=(a,(b,c),(d,e)),试画出其存储结构图（5分）

五、写算法题（20分）

1、假设以带头结点的单链表表示有序表，单链表的类型定义如下：

typedef struct node{

DataType data;

struct node *next

}LinkNode, *LinkList;

编写算法，从有序表A中删除所有和有序表B中元素相同的结点。（6分）2、编写算法在字符串s中删除字符ch。（6分）

3、试编写算法将两个有序的单链表归并成一个新的有序单链表。（8分）

linklist Merge(linklist A, linklist B) /*将有序单链表合并后由函数带回 */

北京理工大学2013级数据结构B试题(A卷)_答案模板

一、选择题 1、从逻辑结构上可以把数据结构分为【 C 】。 A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 2、在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元 素时，需要从后向前依次后移【 B 】个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 3、链表结构不具有下列【 B 】特点。 A、插入和删除无需移动元素 B、可随机访问链表中的任意元素 C、无需实现分配存储空间 D、所需空间与结点个数成正比。 4、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点， 则执行【C】。 A、s->next = p->next; p->next = s; B、p->next = s->next; s->next = p; C、q->next = s; s->next = p; D、p->next = s; s->next = q; 5、一个栈的入栈序列是1，2，3，4，5，则栈不可能输出的序列是【 C 】。 A、54321 B、45321 C、43512 D、12345 6、判断一个队列Q（元素最多为M个）为空的条件是【 C 】。 A、Q->rear – Q->front = M B、Q->rear – Q->front -1 ==M C、Q->rear == Q->front D、Q->rear + 1 == Q->front 7、在一个链队列中，假设f和r分别指向队首和队尾，则插入s所指结点的运算是【 A 】。 A、r->next = s; r=s; B、f->next = s; f=s; C、s->next = r; r=s; D、s->next = f; f=s; 8、深度为5的二叉树至多有【 A 】个结点。 A、31 B、32 C、16 D、10 9、在一非空二叉树的中序遍历序列中，根结点的右边【 A 】。 A、只有右子树上的所有结点 B、只有右子树上的部分结点 C、只有左子树上的所有结点B、只有左子树上的部分结点 10、如果一棵完全二叉树有1001个结点，则其叶子结点个数为【 D 】。 A、250 B、500 C、502 D、490 11、在一个图中，所有顶点的度数之和是所有边数的【 C 】倍。 A、1/2 B、1 C、2 D、4 12、采用邻接表存储的图的深度优先遍历算法类似于二叉树的【 A 】。

数据结构试题集[包含答案_完整版]

第一章概论 一、选择题 1、研究数据结构就是研究（D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i

A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog 2n+n 2+8）,其时间复杂度表示（ C ）。 A. O(n) B. O(nlog 2n) C. O(n 2) D. O(log 2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log 3n) D. O(n 3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（ B ）和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（A ）。 i=s=0; while(s

2013春-数据结构(二)试卷真题

用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是___ _____遍历方法。 3.求图的最小生成树有两种算法，其中______________算法适合于求稀疏图的最小 生成树。 4.求从某源点到其余各顶点的Dijkstra算法在图的顶点数为10，用邻接矩阵表示 图时计算时间约为10ms,则在图的顶点数为40，计算时间约为______ms。 5.设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间复杂度为 ____________。 6.设线性表(a1，a2，…，a500)元素的值由小到大排列。对一个给定的k值，在等概 率情况下，用顺序查找法查找一个记录，查找成功的平均查找长度ASL 为；用二分法检索查找表中与k相等的元素，在查找不成功的情况下至多比较_________次。用分块查找（索引表和各块内均用顺序查找），若分成25块，查找成功的其平均查找长度为___________。 7.在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用折半法查找关键码值8， 需做的关键码比较次数为___ _，查找关键码值20，需做的关键码比较次数为___ _. 8.对于一个高度为h（空树的高度为-1）的A VL树，其最少结点数是。反之， 对于一个有n个结点的A VL树, 其最大高度是，最小高度是。 9.设用希尔排序对数组{98，36，19，5，47，23，1，8，10，7}进行排序，给出的 步长（也称增量序列）依次是5、3、1，则写出第一趟结束后，数组中数据的排列第三个元素是（从0开始计数）。 10.对一组记录（54, 38, 106, 21, 15, 72, 60, 45, 83）进行直接插入排序，当把元素60 插入到有序表时，为寻找插入位置需比较次。 四、简答题（共24分） 1.(8分)已知2棵2-3 树（3阶B-树）如下： （1）对树（a）,请分别画出先后插入26，85两个新结点后的树形； （2）对树（b）,请分别画出先后删除53，37两个结点后的树形。 【解答】： （1）（2）

数据结构2013试题B卷

第 1 页/共 4 页 考试类别[学生填写]（□正考 □补考 □重修 □补修 □缓考 □其它） 1、以下属于逻辑结构的是（ ） A ）顺序表 B ）散列表 C ）有序表 D ）单链表 2、以下算法的时间复杂度为（ ） void fun(int n){ int i=1; while(i<=n) i=i*2; } A ）O(n) B ）O(n 2 ) C ）O(nlog 2 n) D ）O(log 2 n) 3、若线性表最常用的操作是存取第i 个元素及其前驱和后继元素的值，为了提高效率，应采用（ ）的存储方式。 A ）单链表 B ）双向链表 C ）单循环链表 D ）顺序表 4、设线性表中有2n 个元素，（ ）算法，在单链表上实现要比在顺序表上实现效率更高。 A ）删除所有值为x 的元素 B ）在最后一个元素的后面插入一个新元素 C ）顺序输出前k 个元素 D ）交换第i 个元素和第2n – i – 1个元素的值（i=0，…，n-1） 5、栈和队列的主要区别在于（ ） A ）它们的逻辑结构不一样 B ）它们的存储结构不一样 C ）所包含的元素不一样 D ）插入、删除操作的限定不一样 6、设有一个10阶的对称矩阵A[10][10], 采用压缩存储方式按行优先将矩阵中下三角部分的元素存入一维数组B 中，A[0][0]存入B[0]中，则A[8][5]在B 中的位置是( ) A ）32 B ）33 C ）41 D ）65 7、树最适合用来表示（ ）的数据。 A ）有序 B ）无序 C ）任意元素之间具有多种联系 D ）元素之间具有分支层次关系 8、高度为h 的完全二叉树最少有（ ）个结点。 A ）2h B ）2h +1 C ）2h-1 D ）2h -1 9、假设一个有n 个顶点和e 条边的有向图用邻接表表示，则删除与某个顶点v i 相关的所有边的时间复杂度为（ ） A ）O(n) B ）O(e) C ）O(n+e) D ）O(ne) 10、无向图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 ）a ，b ，e ，c ，d ，f B ）a ，c ，f ，e ，b ，d C ）a ，e ，b ，c ，f ，d D ）a ，e ，d ，f ，c ，b 11、对于顺序存储的有序表（5, 12, 20, 26, 37, 42, 46, 50, 64），若采用折半查找，则查找元素26的查找长度为（ ） A ）2 B ）3 C ）4 D ）5 12、采用开放定址法解决冲突的散列查找中，发生聚集的原因主要是（ ） A ）数据元素过多 B ）装载因子过大 C ）散列函数选择不当 D ）解决冲突的方法选择不当 13、若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ） A ）直接插入排序 B ）选择排序 C ）基数排序 D ）快速排序 14、对以下数据序列利用快速排序进行排序，速度最快的是（ ） A ）{21，25，5，17，9，23，30} B ）{25，23，30，17，21，5，9} C ）{21，9，17，30，25，23，5} D ）{5，9，17，21，23，25，30} 15、堆是一种有用的数据结构，下列排序码中序列中，（ ）不是一个堆。 A ）100，85，98，77，80，60，82，40，20，10，66 B ）100，98，85，82，80，77，66，60，40，20，10 C ）10，20，40，60，66，77，80，82，85，98，100 D ）100，85，40，77，80，60，66，98，82，10，20 二、填空题（每空2分，共10分） 下面是折半插入排序算法的实现，请补充完整代码。 void InsertSort(ElemType A[], int len) { int i, j, low, high, mid; for(i=2; i<=len; i++) { A[0]=A[i]; low=1; high=__________; while(__________________) { 线 订 装 郑州轻工业学院2013 — 2014学年 第 1 学期 数据结构 试卷 B 卷 专业年级及班级 姓名 学号

(完整版)数据结构试题及答案

数据结构试卷（一）王彬 一、单选题（每题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进制表示。c A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( d ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二 分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对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．4 10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：____ ____、________、________和_______。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数 为__________个，树的深度为_________，树的度为________。 4.后缀算式9 2 3 +- 10 2 / -的值为________。中缀算式（3+4X）-2Y/3对应的后缀算 式为______3 4X* + 2Y* / -_________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有_______个指针域，其中有________个指针域是存放了地址，有______________个指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有______个和______个。 7.AOV网是一种___________________的图。 8.在一个具有n个顶点的无向完全图中，包含有_____条边，在一个具有n个顶点的有向 完全图中，包含有_____条边。 9.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元 素成为一个子表，则得到的四个子表分别为__________________________、______________、_____________________和_____________________。

数据结构试题试题及答案1

数据结构试题试题及答案1 一、单选题（每小题2分，共8分） 1.在一个长度为n的线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等） 为 C 。 A.n B.n/2 C.(n+1)/2 D.(n -1)/2 2。以下数据结构中哪一个是非线性结构？( D ) A. 队列 B. 栈 C. 线性表 D. 二叉树 3.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( D ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 4.设有6个结点的无向图，该图至少应有( A)条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 5．在下列排序方法中，（ c ）方法平均时间复杂度为0(nlogn)，

最坏情况下时间复杂度为0(n2)；（ d ）方法所有情况下时间复杂度均为0(nlogn)。 a. 插入排序 b. 希尔排序 c. 快速排序 d. 堆排序 6．具有m个结点的二叉排序树，其最大深度为（ f ），最小深度为（ b ）。 a. log 2 m b. └ log2 m ┘ +1 c. m/2 d .┌ m/2 ┐ -1 e. ┌ m/2 ┐ f. m 7．下列排序方法中，属于不稳定的排序方法是(A ) A.直接插入排序法 B.冒泡排序法 C.基数排序法 D.归并排序法 8在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是 ( C ) A.快速排序 B.堆排序 C.归并排序 D.基数排序 9设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示置在676 (10) 用10进制表示。 A．688 B．678 C．692 D．696

考研 数据结构试题(含答案)

我以一名大学生的人格尊严保证，在本场考试中，自觉遵守考试纪律，服从考试管理，决不作弊或帮助别人作弊！签名：学院专业学号级班 ··················密···················封·····················线·················· 命题人签字：系主任签字：审核院长签字：共印份数： 第1页共6页聊城大学计算机学院2012—2013学年第1学期期末考试2011级《数据结构》试题（闭卷B卷） 一、单项选择题（共15题，每题2分，共30分） 1.研究数据结构就是研究（D ）。 A．数据的逻辑结构B．数据的存储结构 C．数据的逻辑结构和存储结构D．数据的逻辑结构、存储结构及其基本操作 2.在数据结构中，从逻辑上可以把数据结构分为（C ）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 3.算法分析的两个主要方面是（A ）。 A．空间复杂度和时间复杂度B．正确性和简单性 C．可读性和文档性D．数据复杂性和程序复杂性 4.下面程序段的时间复杂度是（ C ）。 for(i=0；inext ==NULL

E__Temp2_2013数据结构试题

E__Temp2_2013数据结构试题 2013数据结构试卷 一、选择题(每空题2分共30分) 1．下列关于算法的说法，正确的是（）。 A．程序一定是算法。 B．算法的可行性是指指令不能有二义性。 C．算法可以没有输入但必须有1个以上的输出。 D．算法必须是用计算机语言描述的。 2．从一个具有n个结点的单链表中查找值为x结点，在查找成功情况下，需平均比较（）个结点。 A． n B． n/2 C． (n-1)/2 D． (n+1)/2 3．带头结点的单链表head为空的判定条件是( )。 A． head= =NULL B． head->next==NULL C． head->next= =head D． head!=NULL 4. 循环队列存储在数组A[0..m]中，则入队时的操作为（）。 A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1)mod m D. rear=(rear+1)mod(m+1) 5. 广义表L=((a,b,c))的长度和深度分别是（）。 A.1和1 B.1和3 C.1和2 D.2和3 6．广义表运算式Tail(((a,b),(c,d)))的操作结果是（）。。A．（c,d） B．c,d C．((c,d)) D．（） 7．表达式a*(b+c)-d的后缀表达式是（）。。 A．abcd*+- B．abc+*d- C．abc*+d- D．-+*abcd 8．设n阶方阵A是一对称矩阵，为节省存储空间，将其下三角

（包括对角线）以行序为主序存储在一维数组B(1: n(n+1)/2)中，则对任一上三角元素aij(i A．i(i-1)/2+j B．j(j-1)/2+i C．i(j-1)/2+1 D．j(i-1)/2+1 9．广义表((a))的表头是（）。。 A．a B．(a) C．() D．((a)) 10.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。 A）单链表 B）仅有头指针的单循环链表 C）双链表 D）仅有尾指针的单循环链表 11. 在数据结构中，从逻辑上可以把数据结构分成（）。 A）动态结构和静态结构 B）紧凑结构和非紧凑结构 C）线性结构和非线性结构 D）内部结构和外部结构 12. 在一个不带头结点单链表H中，若要向表头插入一个由指针p 指向的结点，则执行（）。 A. H=p; p->next=H; B. p->next=H; H=p; C. p->next=H; p=H; D. p->next=H->next; H->next=p; 13. 栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 14. 从顺序串中删除一个字符的时间复杂度为( )。 A．O(1) B. O(n) C.O(1og 2n) D. O(nlog 2 n) 15. 以下说法正确的是( )。

数据结构试题及答案(十套)

一、单选题（每题 2 分，共20分） 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点， 则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有 相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n)C．0(n) D．0(n2) 10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、运算题（每题 6 分，共24分） 1.数据结构是指数据及其相互之间的______________。当结点之间存在M对N （M：N）的联系时，称这种结构为_____________________。 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的____首______进行。 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是___top==0___(要超出才为满)_______________。 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。

数据结构试题及答案

数据结构试题及答案 一、选择题(共10题，每题1分，共10分) 1( 下面关于线性表的叙述中，错误的是哪一个,( ) A(线性表采用顺序存储，必须占用一片连续的存储单元 B(线性表采用顺序存储，便于进行插入和删除操作 C(线性表采用链接存储，不必占用一片连续的存储单元 D(线性表采用链接存储，便于插入和删除操作 2( 在一个单链表中，已知q所指结点是p所指结点的前驱，若在p和q之间插入s所指结 点，则执行的操作是( )。 A. s->next=p->next;p->next=s; B. q->next=s;s->next=p; C. p->next=s->next;s->next=p; D. p->next=s;s->next=q; 3( 设有三个元素X，Y，Z顺序进栈，下列得不到的出栈排列是( )。 A(XYZ B. YZX C. ZXY D. ZYX 4( 若用一个长度为6的数组来实现循环队列，且当前rear和front的值分别为0和3， 则从队列中删除一个元素，再增加两个元素后，rear和front的值分别是( )。 A(1和5 B(2和4 C(4和2 D. 5和1 5( 下列说法中正确的是( )。 A(二叉树就是度为2的树 B(二叉树中不存在度大于2的结点

C(二叉树中至少有一个结点的度为2 D(二叉树中任何一个结点的度都为2 6( 在具有n个结点的二叉链表中，共有( )个空指针。 A. n B. n-1 C. n+1 D. 不确定 7( 根据二叉树与树的转换关系可知，深度为h的满二叉树对应的森林由( )棵树构成。 A(1 B(logn C. h/2 D. h 2 8( 在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 A(1/2 B(1 C. 2 D. 4 9( 对17个元素的查找表做折半查找，则查找长度为5的元素下标依次是( )。 A(8,17 ,(5,10,12 C(9,16 D(9,17 10(关于排序，下列说法中正确的是( )。 A. 稳定的排序方法优于不稳定的排序方法，因为稳定的排序方法效率较高 B. 在顺序表上实现的排序方法在链表上也可以实现 C. 在链表上可以实现简单选择排序，但是难以实现堆排序 D. 就平均性能而言，堆排序最佳 二、填空题(共10空，每空2分，共20分) 1( 计算机执行下面的语句时，语句s的执行次数为 _______ 。 for(i=l;i=i;j--) s; 2( 队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_______。 3( 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000 的内存单元中，则元素A[5，5]的地址是_______ 。 4( 一棵有124个叶子结点的完全二叉树，最多有个_______结点。

数据结构试题数据结构试题

数据结构试题3 一、选择题（每小题2分，共8分） 1. 若需要利用形参直接访问实参，则应把形参变量说明为（）参数。 A. 指针 B. 引用 C. 值 2. 在一个单链表HL中，若要在指针q所至结点的后面插入一个由指针p所指向的结点，则执行（）。 A. q->next=p->next; p->next=q; B. p->next=q->next; q=p; C. q->next=p->next; p->next=q; D. p->next=q->next; q->next=p; 3. 在一个顺序队列中，队首指针指向对首元素的（）位置。 A. 后一个 B. 前一个 C. 当前 4．向二叉搜索树中插入一个元素时，其时间复杂度大致为（）。 A. O(long2n) B. O(n) C. O(1) D. O(nlong2n) 二.、填空题（每空1分，共同社2分） 1. 数据的存储结构被分为_______________,________________,_______________和______________四种。 2. 对于一个顺序存储的线性表，在表头插入元素的时间复杂度为______________, 在表尾插入元素的时间复杂 度为_______________。 3. 在稀疏矩阵所对应的三远组线性表中，每个三元组元素按______________为主序，_______________为辅序 的次序排列。 4. 在广义表的存储结构中，单元表结点与表元素结点有一个域对应不同，各自分别为_______________域

和_______________域。 5. 中级表达式3+x*(2.4/5-6)所对应的后缀表达式为_________________。 6. 在一棵高度为h的3叉树中，最多含有_______________结点。 7. 假定一棵二叉树的结点数为18，则它的最小深度为_______，最大深度为______。 8. 在一课二叉树搜索中，每个分支结点的左子树上所有的结点的值一定______该结点的值，右子树上所有的结 点的值一定_____该结点的值。 9. 当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层______调整，知道被调整到______位置为止。 10. 表示图的三种存储结构为________________，_________________和_________________。 11. 对用邻接矩阵表示的具有n个定点和e条边的图进行任一种遍历时，其时间复杂度为__________，对用邻接 表表示的图进行任一种遍历时，其时间复杂度为______________。 12. 从有序表（12，18，30，43，56，78，82，95）中依次二分查找43和56元素时，其查找长度分别为______和______。 13. 假定对长度n=144的线性表进行索引查找，并假定每个子表的长度均为，则进行索引查找的平均查找长度 为_______，时间复杂度为________________。 14. 一棵B_树中的所有叶子结点均处在_______________上。 15. 每次从无序表中顺序取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做______排序；每 次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做______排序。 16. 快速排序在平均情况下的时间复杂度为________________，在最环情况下的时间复杂度为 ______________。 三.、运算题（每小题6分，共24分） 1．假定一棵普通树的广义表表示a(b(e),c(f(h，i)，g)，d)，分别写出先根、后根、按层遍历的结果。

2012-2013(2)数据结构A卷及参考答案资料

一、填空题（每空1 分，共10分） 1．向一个长度为n的向量的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动n-i+1个元素。 2．带有一个头结点的单链表head为空的条件是head->next=head。 3．由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为44 。 4．设s=’I︺AM︺A︺TEACHER’，其长度是 14 。 5．二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200，则A[6][12]的地址是326。 6．假设在有序线性表A[1..20]上进行二分查找，则比较一次查找成功的结点数目个数为__ 1__。 7.深度为k的完全二叉树至少有2k-1个结点，至多有2k-1个结点。8．在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i ]等于1。9．执行广义表操作GetTail[ GetHead[ ((a,b),(c,d)) ] ]后的结果为（b）。 二、选择题（每小题1分，共10分） 1.下列数据中，哪一个是非线性结构？( D ) A. 栈 B. 队列 C. 字符串 D. 二叉树 2.设P指向单链表的某个节点，在P之后插入一个节点S的操作为( C) A. P->next = S; B. P->next = S->next; S->next = P->next; C. S->next = P->next; P->next = S; D. P->next = S; P = P->next; 3．设三个元素的进栈顺序为abc，则下列哪个序列是不可能出现的出栈序列( D) A. abc B. acb C. cba D. cab 4 ．假设用块链存储结构表示串，如果每一个块的大小为4个字符（每个字符占用一个字节），一个指针占4个字节，则一个长为15的串需要多少字节的存储空

数据结构期末试题及答案

E 卷一、单项选择题 1、线性表若采用链式结构时，要求内存中可用存储单元的地址 ( )。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续不连续都可以 2、判定一个栈ST(最多元素为m0)为空的条件是( ) 。 A. ST->top!=0 B. ST->top==0 C. ST->top!=m0 D. ST->top==m0 3、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列j下标从1 到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5] 的起始地址为 ( ) 。 A. SA+141 B. SA+144 C. SA+222 D. SA+225 4、设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7 其余地址为空 如用二次探测再散列处理冲突，关键字为 49的结点的地址是( )。 A. 8 B. 3 C. 5 D. 9 5、在线索化二叉树中， t所指结点没有左子树的充要条件是 ( )。 A. t->left==NULL B. t->ltag==1 C. t->ltag==1且t->left==NULL D. 以上都不对 6、将递归算法转换成对应的非递归算法时，通常需要使用 ( ) 。

A. 栈 B. 队列 C. 链表 D. 树 7、有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100}, 当二分查找值为82的结点时， ( )次比较后查找成功。 A. 1 B. 2 C. 4 D. 8 8、对一个满二叉树， m个树叶， n个结点，深度为h，则( )。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h -1 9、如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用_____查找方法。 A. 分块 B. 顺序 C. 二分 D. 散列 10、快速排序方法在( )情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数 11 、在含有n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为________. A.e B.2e C. n 2 -e D. n 2 -2e 12.假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点V 相关的所有弧的时间复杂度是_________. i A.O(n) B.O(e) C.O(n+e) D.O(n*e) 13. 用某种排序方法对关键字序列( 25， 84， 21， 47， 15， 27， 68， 35，20)进行排序时，序列的变化情况：

2013山西省数据结构基础试题及答案

2013山西省数据结构基础试题及答案 1、下面关于线性表的叙述中，错误的是哪一个？（ D ） A）线性表采用顺序存储，必须占用一片连续的存储单元。 B）线性表采用链接存储，便于插入和删除操作。 C）线性表采用链接存储，不必占用一片连续的存储单元。 D）线性表采用顺序存储，便于进行插入和删除操作。 2、（ C ）在进行插入操作时，常产生假溢出现象。 A）顺序栈 B）循环队列 C）顺序队列 D）链队列 3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ D ）存储方式最节省时间。 A）顺序表 B）双链表 C）带头结点的双循环链表 D）单循环链表 4、设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（ B ）。 A）3，2，5，6，4，1 B）1，5，4，6，2，3 C）2，4，3，5，1，6 D）4，5，3，6，2，1 5、下面关于线性表的叙述中，错误的是哪一个？（ D ） A）线性表采用顺序存储，必须占用一片连续的存储单元。 B）线性表采用链接存储，便于插入和删除操作。 C）线性表采用链接存储，不必占用一片连续的存储单元。 D）线性表采用顺序存储，便于进行插入和删除操作。 6、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（ A ）。

A）直接选择排序 B）直接插入排序 C）快速排序 D）起泡排序 7、下列序列中，执行第一趟快速排序后得到的序列是（ A ）。 A）[d,a,e,d,b]f[h,g] B) [c,e,a,d]f[h,g,b] C) [g,a,e,c,b]f[d,h] D) [a,b,c,d,]f[e,g,h] 8、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A) 单链表 B) 仅有头指针的单循环链表 C) 双链表 D) 仅有尾指针的单循环链表 9、n个顶点的强连通图至少有（ A ）条边。 A）n B）n+1 C）n-1 D）n(n-1) 10、二叉树第i(i≥1)层上至多有（ C ）结点。 A）2i B）2i C）2i-1 D）2i-1 11、以下属于顺序存储结构优点的是（ A ）。 A) 存储密度大 B) 插入运算方便 C）删除运算方便 D）可方便地用于各种逻辑结构的存储表示 12、下面关于线性表的叙述中，错误的是哪一个？（ D ） A）线性表采用顺序存储，必须占用一片连续的存储单元。 B）线性表采用链接存储，便于插入和删除操作。 C）线性表采用链接存储，不必占 用一片连续的存储单元。 D）线性表采用顺序存储，便于进行插入和删除操作。 13、线性表的链接实现有利于（ A ）运算。

2012-2013数据结构试题12050841

2012-2013 学年第2 学期末考试试题（A卷） 课程名称计算机程序设计基础__________ 使用班级：12050841 _______ 、判断题（共20 分每小题2 分） 1不论是入队操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（）2当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（） 3完全二叉树中的叶子结点只可能在最后两层中出现。（） 4哈夫曼树中没有度数为1的结点。（） 5对连通图进行深度优先遍历可以访问到图中的所有顶点。（） 6先序遍历一查二叉排序树一定可以得到一个有序序列。（） 7线性表中的所有元素都有一个前驱元素和一个后继元素。（） 8满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（） 9调用一次深度优先遍历算法可以访问到图中的所有顶点。（） 10栈和队列的共同特点是只允许在表的一端进行插入和删除操作。

二、运算题（共40分） 1请根据你的理解，给出数据结构的定义。（6分） 2请给出稀疏矩阵的概念，举一实例，并给出此实例的三元组表示。（10分） 3有6个元素A B、C D E F一次进栈，允许任何时候出栈，能否得到下列的每个出栈序列, 若能，给出栈操作的过程，若不能，简述其理由。（10分） (1) CDBEFA (2)ABEDFC (3)DCEABF (4)BAEFCD

4 一个AOV网的二元组表示为： V={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} E={<0,2>,<0,4>,<1,2>,<1,5>,<2,4>,<3,5>,<4,6>,<4,7>,<5,7>,<6,8>,<7,6>,<7,8>,<7,9>,< 8,10>,<9,10>} 在此AOV网的邻接表存储中，若各顶点邻接表中的边接结点是按照邻接顶点序号从大到小链接 的，请写出按此邻接表和介绍的拓扑排序算法得到的拓扑序列。提示：先画出图形再运算。（14分，画出图形得4分，正确写出拓扑序列得10分） 三、算法设计题（40分） 1 从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息 并停止运行，设单链表的节点类型为Lnode。（10分） Struct Lno de{ int data; Lno de* n ext;

数据结构试题集（8套卷子+答案）

数据结构试题集（8套卷子+答案） 《数据结构》试卷一 一、填空题：（共２０分） 1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。 2、队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是。 3、在一棵二叉树中，度为０的结点个数为n0，度为２的个数为n2，则n0= 。 4、二叉树的前序遍历序列等同于该二叉树所对应森林的遍历序列 5、对一棵二叉排序树，若以遍历该树，将得到一个以关键字递增顺序排列的有序序列。 6、三个结点a,b,c组成二叉树，共有种不同的结构。 7、在AVL树中，由于在Ａ结点的右孩子的右子树上插入结点，使Ａ结点的平衡因子由-1变为-2，使其失去平衡，应采用型平衡旋转。 8、图的遍历有两种,它们是。 9、堆排序的时间复杂度为。 10、在含有N个结点的二叉链表中有空链域，通常用这些空链域存储线索，从而得另一种链式存储结构----线索链表。 二、单项选择题（共２０分） １、若进栈序列为１，２，３，４，假定进栈和出栈可以穿插进行，则可能的出栈序列是（） （A）２，４，１，３（B）３，１，４，２ （C）３，４，１，２（D）１，２，３，４ ２、有一棵非空的二叉树，（第０层为根结点），其第i层上最多有多少个结点？（）（A）２i（B）２1-i（C）２1+i（D） i ３、设电文中出现的字母为A，B，C，D，E，每个字母在电文中出现的次数分别为９，２７，３，５，１１，按huffman编码，则字母A编码为（）

（A）１０（B）１１０（C）１１１０（D）１１１１ ４、下面关于数据结构的叙述中，正确的叙述是（） （A）顺序存储方式的优点是存储密度大，且插、删除运算效率高（B）链表中每个结点都恰好包含一个指针 （C）包含n个结点的二叉排序树的最大检索长度为log n 2 （D）将一棵树转为二叉树后，根结点无右子树 ５、程序段：y:＝0 while n>=(y+1)*(y+1) do y:=y+1 enddo 的时间复杂度为（） （A）O(n) （B）O(n2) （C）O(n2/1) （D）O(1) 6、排序方法中,关键码比较的次数与记录的初始排列无关的是( ) (A) shell排序 (B) 归并排序 (C) 直接插入排序 (D) 直接选择排序 7、数组q[0..n-1]作为一个环行队列,f 为当前队头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数总小于n,则队列中元素个数为( ) (A) r-f (B) n+f-r (C) n+r-f (D) (n+r-f) mod n 8、为了有效的利用散列查找技术,需要解决的问题是:( ) Ⅰ:找一个好的散列函数 Ⅱ:设计有效的解决冲突的方法 Ⅲ:用整数表示关键码值 (A) Ⅰ和Ⅲ (B) Ⅰ和Ⅱ (C) Ⅱ和Ⅲ (D)Ⅰ,Ⅱ和Ⅲ 9、引入线索二叉树的目的是（） (A) 加快查找结点的前驱或后继的速度 (B) 为了能在二叉树中方便的进行插入与删除 (C) :为了能方便的找到双亲 (D) 使二叉树的遍历结果唯一