数据结构试题一．选择题1．数据结构每个结点存放一个数据元素，各结点存储在连续的存储空间，称为______存储方式

一．选择题

1．数据结构每个结点存放一个数据元素，各结点存储在连续的存储空间，称为______存储方式

A）顺序 B）链式 C）索引 D）散列

3.设有一个栈，按A、B、C、D的顺序进栈，则可能的出栈序列是 ( )

4．队列是限制在______处进行插入操作的线性表 （ ）

5.除根结点外，树上每个结点 ( )

6.若有四个数字5、6、7、8顺序进入队列，则其队尾元素为 ( )

7．串S值为“abcdef”，则函数Length（S）的值为 （ ）

9.深度为k的二叉树至多有 ( )

10.下列排序方法中，属于稳定的排序方法是（　　　）

二．填空题

1．数据结构包括：_________，数据的逻辑结构包括：____________

3．队列特点是__________________；栈的特点是_______________

4．一个深度为K的二叉树中，最多可有___________个结点

5．对于具有n个元素的有序序列，若采用冒泡排序，所需的比较次数为___________次。

6．二叉树的遍历可分为：先序遍历、中序遍历和_____________

三．应用题

1．字符与字符串的区别

2．如下程序段，计算程序语句执行的时间复杂度（写出计算过程）

for (a=1; a<=n; a++)

for (b=1; b<=a; b++)

s++;

3．设串 S= ”I　AM　A　BOY” ， T= ”LITTLE” ，Q= ”GIRL”

求：1）StrLength（S） ； 2）SubStr（S，6，5） ； 3）StrRep（S，”BOY”，Q）；

4）StrConcat（SubStr（S，6，2），StrConcat（T，SubStr（S，7，4）））

4．有二维数组A［5］［6］，采用按行为主序的存储方式，每个元素占3个存储单元，若A［0］［0］的存储地址是100，则计算A［4］［3］的存储地址 （注：写出计算过程）

5．有如下稀疏矩阵A，写出该稀疏矩阵的三原组表

6．有如下二叉树，求：1）树的度； 2）树的深度； 3）写出先序遍历、中序遍历、后序遍历时，结点的访问次序

A

B C

D E F G

H I J

四．程序设计题

编写程序实现如下功能： 1）创建一个数组，输入初始数据（例如5个数据），输出； 2）升序排列数组并输出； 3）从键盘插入一个新数据至数组相应位置，输出； 4）查找一个指定的数据（在数组中），如找到则删除该数据，输出数组，否则显示查无此数； 5）倒序存储，输出

这是三题应用题第6小题的图