一、 选择(2分×10)
1． 数据结构的基本单位是（ ）
a．数据项b．数据元素c．数据结构d．数据类型。
2． 在等概率的情况下，有n个结点的顺序表上做删除结点运算，需平均移动节点的数目为（ ）
a．nb．(n-1)/2
c．n/2d．(n+1)/2
3． 在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是（ ）
a．p=nullb．p->next->next =h
c．p=hd．p->next=h
4． 若进栈序列为abc，则通过入、出栈操作可能得到的abc的不同排列个数为（ ）
a．4b．5c．6d．7
5． 用链表方式存储的队列，在进行删除运算时（ ）
a．仅修改头指针b．仅修改尾指针。
c．头、尾指针都要修改d．头、尾指针都可能要修改。
6． 中序序列为abc的不同二叉树有几种（ ）
a．3b．4c．5d．6
7． 下列数据结构是非线性结构的是（ ）
a．队列b．树c．栈d．串。
8． 以下论述正确的是（ ）
a．空串与空格串是相同的。
b．“tel”是“teleptone”的子串
c．“student”<“student”
d．空串的长度为1
9． 在一个链队列（队列中元素个数大于2个）中，假设front和rear分别为队首和队尾指针，则删除一个结点的运算是（ ）
a．rear=front->nextb．rear=rear->next;
c．front=front->nextd．f=rear->next;
10． 对一棵满二叉树，m个叶子，n个结点，深度为h，则（ ）
a． n=h+mb． h+m=2n c． m=h-1 d．n=2h-1
二、 填空(1分×15)
1． 串是一种特殊的线性表，其特殊之处在于。
2． 在具有n个单元的循环队列中，队满时共有个元素。
3． 栈的特点是队列的特点是表。
4． 二维数组a的元素是单个字符，行下标i的范围是1~5，列下标范围是1~6，a按行优先存储时元素a[3][5]的起始地址与a按列优先存储时元素的起始地址相同。
5． 深度为k的完全二叉树共有n的结点，则n若自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是。
6． 已知完全二叉树第8层有8个结点，则其叶结点个。
7． 数据结构的存储结构有四种。
8． 下面算法的时间复杂度是。
i=1;k=0;
while( i<=n-1)
k+=10*i;
i++;9． 设串s1=”abcdefg”，s2=”pqrs”，则concatstr(substr(s1,2,lenstr(s2)) substr(s1,lenstr(s2),2))的结果串为。
三、 判断题(1分×5)
1． 顺序存储结构只能用于存储线性结构。（
2． “bei” 是“bei jing”的子串。（
3． 所有二叉树的叶子结点的个数比度为2的结点个数多1个。（
4． 二叉树的先序遍历序列中，任一个结点均处在其孩子结点的前面。（
5． 循环队列中没有溢出现象。（
四、 简答题（60分）
1． （9分）某二叉树的结点数据采用顺序存储，其结构如下：
1） 画出该二叉树的二叉链表存储结构。
2） 写出该二叉树的先序遍历序列，中序遍历序列，后序遍历序列。
3） 画出该二叉树的中序线索二叉树。
2． （4分）一棵度为3的树有10个度为1的结点，20个度为2的结点，30个度为3的结点，则该树共有多少个叶子结点？（写出计算过程）
3． （4分）绘制广义表l=(a,(b),(c,(d)))的头尾表示法存储结构。
4． （6分）已知一棵二叉树的后序遍历和中序遍历的序列分别为：acdbgihfe和abcdefghi。请画出该二叉树，并写出它的先序遍历的序列为。
5． （10分）设顺序栈的存储结构如下，请实现栈基本操作。
#define maxlen 100
typedef int datatype;
typedef struct stacknode
datatype data[maxlen];
int top;
seqstack;
seqstack* initstack() 栈的初始化，申请空间并置空栈。
void push（seqstack *s, datatype x） /x 入栈。
void pop（seqstack *s, datatype *x）//出栈并打印输出。
int sempty(seqstack *s) /判断栈空，栈空返回1并输入“栈空”，栈不空返回0
int sfull(seqstack *s) /判断栈满，栈满返回1并输出“栈满”，栈不满返回0
void main( )
seqstack *s;
datatype e;
s=initstack( )
scanf(“%d”, e);
while(e>0 &&sfull(s)==0)
while(sempty(s)==0)
6． （10分）下述算法的功能是在一个递增有序的顺序表l中，插入x后使l仍为有序表，在空白处填写适当的内容。
typedef int datatype;
typedef struct
datatype data[maxlenmaxlen为顺序表的最大容量。
int last表长。
seqlist;
int insert (seqlist *l, datatype x)
int j;
if( ①printf(“顺序表已满，不能插入”);
j=l->last-1从表尾开始比较。
while(j>0大于x的结点后移。
l->data[j+1后移。
插入新结点。
7． （10分）下面程序是把两个串r1和r2首尾相连，即r=r1+r2，试完成程序填空。
#define maxlen 20
typedef struct
char vex[maxlen];
int lenlen为串的长度。
str;void concatstr(str *r1, str *r2)
int i;
printf(“%s%s”, r1->vex,r2->vex);
if(r1->len + r2->len>
printf(“两个串太长，溢出”)；
else for(i=0; i< ②i把r2连接到r1
r1->vecr2->vec[i];
r1->vec[r1->len+i添上字符串结束标志。
r1->len修改新串长度。
8． （7分）设一个循环队列queue，只有头指针front，不设尾指针，另设一个count变量记录队列中的元素个数，试写出这种循环队列的结构体声明以及对应的入队算法和出队算法。
数据结构练习
一 选择题 1 若长度为n的线性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动 个数据元素。a 2.在单链表中，已知q指的结点是p指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行b a.q next p s next p b.s next p q nex...
数据结构练习
第1章。1.从逻辑上可以把数据结构分为。a 动态结构 静态结构 b 顺序结构 链式结构。c.线性结构 非线性结构 d 初等结构 构造型结构。2.关于算法的描述，不正确的是。a.算法最终必须由计算机程序实现。b 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。c.健壮的算法不会因非法的输人数...
数据结构练习
一 选择题。1 广度优先遍历的含义是 从图中某个顶点v出发，在访问了v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，且 先被访问的顶点的邻接点 先于 后被访问的顶点的邻接点 被访问，直至图中所有已被访问的顶点的邻接点都被访问到是下图的广度优先遍历序列。a.1 ...