内容发布更新时间 : 2024/11/20 12:21:47星期一 下面是文章的全部内容请认真阅读。

1

第一部分 线性 一.选择题（共10题） 1.以下说法正确的是（）。

A.数据元素是数据的最小单位。B. 数据结构是带结构的各数据项的集合。 C.数据项是数据的基本单位。D. 数据结构是带结构的数据元素的集合。 2. 在设计存储结构时，通常不仅要存储各数据元素的值，而且还要存储（）。 A.数据的处理方法

B.数据元素的类型 D.数据的存储方法

D.一对多

C.数据元素之间的关系 A.一对一

3.树状结构中的数据元素之间存在（）逻辑关系。

B.多对一

C.多对多

4.以下数据结构中，哪一个不属于线性结构（）。 A.串 B.广义表 C.栈 D.树

5.对一个具有n个结点的单链表，在表头位置插入其值等于x的结点时，操作的时间复杂度为（）。 A. O(1)

B. O(x)

C. O(n)

D. O(n2)

6. 设一顺序栈已含3个元素a（栈底）、b、c（栈顶），元素d正等待进栈。那么下列4个序列中不可能出现的出栈序列是（）。

A. dcba B. cdba C. cbda D. cadb 7. 如果栈采用顺序存储结构，则入栈操作时（）。

A. 必须判别栈是否满。 B. 必须判别栈是否空。 C. 判别栈元素的类型。 D. 对栈不做任何操作。

8.用一个大小为N的数组来实现循环队列Q，假定front和rear分别为队头指针和队尾指针，判断该循环队列为满的条件是（）。

A.(Q.rear+1)==Q.front B. Q.front==Q.rear C.(Q.rear+1)%N==Q.front D. (Q.front+1)%N==Q.rear 9.串S=“串string”的长度是（）。

A. 6 B. 7 C. 8 D. 9

10.设二维数组arr[6][4]（行列下标从0开始）的每个元素占6个单元，按行优先顺序存放在起始地址为2000的连续内存单元中，则存储地址为2066的是元素（）。 A. arr[2][3] B. arr[3][3] C. arr[5][1] D. arr[4][1] 二.填空题（共25空）

1.根据数据元素之间关系的不同特性，通常有4类基本数据结构，它们是: (____________)、(___________)、(___________)、(___________)。

2.在数据结构中，(______________)用于完整地描述一个研究对象，是数据的基本单位。 3.计算机中的算法指的是解决某类问题的有限操作序列，它必须具备输入、输出、(____________)、(______________)、(______________)等5个特性。

2

4.顺序表中逻辑上相邻的元素的物理位置(___________)。 5.下面程序段的时间复杂度是(___________)。 int r=1; int i=1; while(i

6.循环单链表H中，指针P所指结点是表尾结点的判断条件是(___________)。

7. 在线性表A,采用单链表存储，已经有数据（b,c,d,e,f,h）中，要删除元素c，此时已经有指针p指向b元素，语句为：q=p->next; (___________); x=q->data;free(q);

要插入元素g，使得此线性表变为（b,c,d,e,f,g,h）,此时已经有指针p指向f元素，插入g的语句为：s->data=‘g’，s->next= (___________); p->next=s;

8. 设有一顺序栈S，元素A、B、C、D、E、F依次进栈，如果6个元素出栈的顺序是A、D、F、E、C、B，则栈的容量至少应该是(___________)。

9.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做入栈处理时，top变化为(___________)。

10.设有一空栈，现有输入序列a，b，c，d，e，操作push代表入栈，pop代表出栈，经过push，push，push，pop，push，pop，pop后，栈顶元素为(___________)。

11. 用一个大小为10的数组来实现循环队列，且当前队头和队尾的值分别为2和7，当从队列中删除3个元素，再加入4个元素后，rear的值为(___________)，front的值为(___________)，当前队列的长度为(___________)。

12.若Replace(S,V,T)表示用字符串T替换主串S中的所有子串V的操作，则对于S=“software”，V=“ware”，T=“ly”，Replace（S,V,T）=(___________)。

13.设二维数组A[6][4]（行列下标从0开始）的每个元素占6个单元，将其按列优先顺序存放在起始地址为200的连续内存单元中，则元素a[4][3]的地址为(___________)。

14.广义表(b,(d,a),(c,e)) （其中，a、b、c、d、e是原子）的深度为(___________)，长度为(___________)，表头为(___________)，表尾为(___________)。 三.应用题

1.利用算符优先算法对表达式#(7 – 3)× 5 #求值，写出操作符栈和操作数栈在任意时刻的状态。 2.已知L是带头结点的单链表的头指针，链表结点定义如下： typedef struct LNode { int data; // 数据域 struct LNode *next; // 指针域 } LNode，* LinkList;

请写算法统计并输出单链表L中小于x的数据元素的个数。 void count(LinkList L, int x)

i ++;

3

三、解答：