山东建筑大学数据结构考试题

要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。

一、单项选择题（每小题1.5分，共计30分）

1. 数据结构是指 。 A. 一种数据类型 B. 数据的存储结构

C. 一组性质相同的数据元素的集合

D. 相互之间存在一种或多种特定关系的数据元素的集合 2. 以下算法的时间复杂度为 。

void fun(int n) { }

int i=1; while (i<=n)

i++;

A. O(n) B. O(n)

C. O(nlog2n) D. O(log2n)

3. 在一个长度为n的有序顺序表中删除元素值为x的元素时，在查找元素x时采用二分查找，此时的时间复杂度为 。

A. O(n) C. O(n2)

B. O(nlog2n) D. O(n)

4. 在一个带头结点的循环单链表L中，删除元素值为x的结点，算法的时间复杂度为 。

A. O(n)

B. O(n)

C. O(nlog2n) D. O(n2) 5. 若一个栈采用数组s[0..n-1]存放其元素，初始时栈顶指针为n，则以下元素x进栈的正确操作是 。

A.top++;s

要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。

一、单项选择题（每小题1.5分，20小题，共计30分）

1. 以下数据结构中 属非线性结构。 A.栈 B.串 2. 以下算法的时间复杂度为 。

void func(int n) { int i=0,s=0; while (s<=n) { i++; s=s+i; } }

C.队列 D.平衡二叉树

A. O(n)

B. O(n) D. O(log2n)

C. O(nlog2n)

3. 在一个双链表中，删除p所指节点（非首、尾节点）的操作是 。 A.p->prior->next=p->next;p->next->prior=p->prior; B.p->prior=p->prior->prior;p->prior->prior=p; C.p->next->prior=p;p->next=p->next->next;

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

4. 设n个元素进栈序列是1、2、3、…、n，其输出序列是p1、p2、…、pn，若p1=3，则p2的值为 。

A.一定是2

第一部分 选择题(30分)

一、选择题（20分）

1．组成数据的基本单位是（ ）。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量

2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ ）。

(A) 线性结构

(B) 树型结构 (C) 图型结构 (D) 集合

3．数组的逻辑结构不同于下列（ ）的逻辑结构。 (A) 线性表 (B) 栈 (C) 队列 (D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（ ）个。

(A) 2i (B) 2i (C) 2i-1 (D) 2i-1

5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ ）。

(A) p->next=p->next->next (C) p=p->next->next

(B) p=p->next (D) p->next=p

6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ ）。 (A) 6 (B) 4 (C) 3

第一部分 选择题(30分)

一、选择题（20分）

1．组成数据的基本单位是（ ）。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量

2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ ）。

(A) 线性结构

(B) 树型结构 (C) 图型结构 (D) 集合

3．数组的逻辑结构不同于下列（ ）的逻辑结构。 (A) 线性表 (B) 栈 (C) 队列 (D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（ ）个。

(A) 2i (B) 2i (C) 2i-1 (D) 2i-1

5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ ）。

(A) p->next=p->next->next (C) p=p->next->next

(B) p=p->next (D) p->next=p

6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ ）。 (A) 6 (B) 4 (C) 3

数据结构习题集含答案

目录

目录 ............................................................................................................................. 1 选择题 ......................................................................................................................... 2

第一章绪论 ................................................................................................................................................. 2 第二章 线性表 ..............................................................................................

数据结构试题一

一、单项选择题（每小题3分，共30分）

1、在有n 个叶子结点的哈夫曼树中，其结点总数为（ ）。 A、不确定 B、2n C、2n+1 D、2n-1 2、下列序列中，（ ）是执行第一趟快速排序得到的序列（排序的关键字类 型是字符串）。

A、[da，ax，eb，de，bb]ff[ha，gc] B、[cd，eb，ax，da]ff[ha，gc，bb] C、[gc，ax，eb，cd，bb]ff[da，ha] D、[ax，bb，cd，da]ff[eb，gc，ha]

3、若线性表最常用的操作是存取第 i 个元素及其前驱的值，则采用（ ） 存储方式节省时间。

A、单链表 B、双链表 C、单循环链表 D、顺序表 4、下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlogn)的是 （ ）。 A、堆排序 B、冒泡排序 C、直接选择排序 D、快序排序

5、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的 二叉树。

A、空

第七章 图

一、选择题

1．图中有关路径的定义是（ ）。【北方交通大学 2001 一、24 （2分）】

A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为n，则该图最多有（ ）条边。

2

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n 【清华大学 1998 一、5 （2分）】【西安电子科技大 1998 一、6 （2分）】 【北京航空航天大学 1999 一、7 （2分）】

3．一个n个顶点的连通无向图，其边的个数至少为（ ）。【浙江大学 1999 四、4 (4分)】

A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有n个顶点的有向图，至少需要（ ）条边。【北京航空航天大学 2000 一、6(2分）】

A．n-l B．n C．n+l

安徽大学数据结构

一、填空题

1、算法的5个重要特性是_____有穷性_____、___确定性________、___可行性_____、输入和输出。

2、单链表中，除首元素结点外，其它任一元素结点的存储位置由__其前驱的指针域_________指示。

3、在双向链表中，欲在p所指结点之前插入一个由s指向的结点，请完成有关操作。 s->prior=p->prior; p->prior=s; p->next=s->next； s->next=p;

4、对于栈只能在____栈顶____插入和删除元素；对于队列只能在___队尾______插入元素和__队头_____删除元素。

5、在模式匹配的KMP算法中用到了一个next函数，若next[j]=k，则说明在模式串T中存在一个与“T1T2...Tk-1”相等的子串“__Tj-k+1?.Tj-1_______________”。

6、假设有二维数组A6?8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A共占用_____288_______个字节的存储单元，按行存储时，元素A25的第一个字节的地址为______1126______

1. 下面程序段的执行次数为（ A ）

for(i=0;i＜n-1;i++)

for(j=n;j＞i;j--)

state;

A. n(n+2)2 B .(n-1)(n+2)2 C. n(n+1)2 D. (n-1)(n+2)

2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ B ）A. 110 B .108 C. 100 D. 120

3. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（ C ）A. edcba B .decba C. dceab D. abcde

4. 循环队列用数组A[0,m－1]存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是（ D ）

A. (rear-front+m)%m B .read-front+1C. read-front-1 D. read-front

5．不带头结点的单链表head为空的判定条件是（ A ）A. head=NULL B .head-next=NULLC. head-next=head

山东省 专升本 数据结构 计算机

山东：07年专升本考试数据结构模拟试题1

专升本《数据结构》试卷

一、填空题：（每小题2分，共10分）

1. 设有数据结构（D，R），其中 D 是数据元素的有限集，R 是 的有限集。

2. 深度为 k 的二叉树其结点数至多有 个。

3. 栈是一种特殊的线性表，它允许在表的一端进行 操作。

4. 通常象交通、道路问题的数学模型是一种称为 的数据结构。

5. 哈希表是一种查找表，可以根据哈希函数直接获得 。

二、单项选择题：（每小题2分，共10分）

对于下列各题，在备选答案中选出一个正确的，并将其编号填在“ ”位置上。

1. 若线性表最常用的操作是存取第 i 个元素及其前驱元素的值，则采用 存储方式最节省运算时间。

A. 单链表 B. 双链表 C. 单循环链表 D. 顺序表

2. 下列排序算法中， 算法在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。。

A. 直选择排序 B. 冒泡排序 C. 归并排序 D. 堆排序

3. 队列的操作原则是 。

A. 先进后出 B. 先进先出 C. 只能进行插入 D. 只能进行删除

4. 在具有 n 个结点的二叉链表中，非空的链域个数为 。

A. n-1 B. n C. n 1 D. 不确定

5.