2015-2016-1《数据结构》期中考试试卷。
cdaba bdccc bacdb daddb bccdc cdabc bcacc
一、选择题(每题2分，共70分)
1．具有线性结构的数据结构是（ ）
a．树 b．图。
c．栈和队列 d．广义表。
2. 下面几种算法时间复杂度阶数中，值最大的是（ ）
3.下述哪一条是顺序存储结构的优点？（
a．存储密度大 b．插入运算方便 c．删除运算方便 d．可方便地用于各种逻辑结构的存储表示。
4．下面关于线性表的叙述中，错误的是哪一个？（
a．线性表采用顺序存储，必须占用一片连续的存储单元。
b．线性表采用顺序存储，便于进行插入和删除操作。
c．线性表采用链接存储，不必占用一片连续的存储单元。
d．线性表采用链接存储，便于插入和删除操作。
5．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
a．顺序表 b．双链表 c．带头结点的双循环链表 d．单循环链表。
6．链表不具有的特点是（ ）
a．插入、删除不需要移动元素 b．可随机访问任一元素
c．不必事先估计存储空间 d．所需空间与线性长度成正比。
7. 下列关于队列的叙述中，错误的是( )
a.队列是一种先进先出的线性表。
b.队列是一种后进后出的线性表。
c.循环队列中进行出队操作时要判断队列是否为空。
d.在链队列中进行入队操作时要判断队列是否为满。
8. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）1<=i<=n+1)。
a. o(0) b. o(1c. o(nd. o(n2)
9. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）
a．o(n) o(n) b. o(n) o(1) c. o(1) o(n) d. o(1) o(1)
10．在双向链表指针p的结点前插入一个指针q的结点操作是（ ）
a. p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=q；
b. p->llink=q;p->llink->rlink=q;q->rlink=p;q->llink=p->llink;
c. q->rlink=p;q->llink=p->llink;p->llink->rlink=q;p->llink=q;
d. q->llink=p->llink;q->rlink=q;p->llink=q;p->llink=q;
11.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是( )
a）110 （b）108 （c）100 （d）120
12. 链接存储的存储结构所占存储空间：(
a） 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。
b） 只有一部分，存放结点值。
c） 只有一部分，存储表示结点间关系的指针。
d） 分两部分，一部分存放结点值，另一部分存放结点所占单元数。
13． 单链表的存储密度( )
ａ）大于1； （等于1； （小于1； （不能确定。
14.若元素的入栈顺序为1，2，3...n，如果第2个出栈的元素是n，则输出的第i(1<=i<=n)个元素是( )
d.无法确定。
15．假设以数组a[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（ ）
a．3 b．37
c．50 d．97
16.下列关于队列的叙述中，错误的是( )
a.队列是一种先进先出的线性表。
b.队列是一种后进后出的线性表。
c.循环队列中进行出队操作时要判断队列是否为空。
d.在链队列中进行入队操作时要判断队列是否为满。
17.一个队列的输入序列是a，b，c，d，则该队列的输出序列是( )
18.队列的特点是（ ）
a.允许在表的任何位置进行插入和删除。
b.只允许在表的一端进行插入和删除。
c.允许在表的两端进行插入和删除。
d.只允许在表的一端进行插入，在另一端进行删除。
19.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（ ）
20.设栈的初始状态为空，元素依次入栈，得到的出栈序列是（2,4,3,6,5,1）,则栈的容量至少是( )
a.2 b.3
c.4 d..6
21．若栈的进栈序列为1，2，3，4，5，则经过出入栈操作不可能获得的出栈序列是( )
a．4，5，3，2，1 b．4，3，5，1，2
c．1，2，3，4，5 d．5，4，3，2，1
22.已知一个栈的入栈序列是1，2，3，…，n，其输出序列为pl，p2，p3….，pn，若p1是n，则pi是（ ）
d.不确定。
23．设有一个10阶的下三角矩阵a，采用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a85的地址为 （
a．1012 b．1017
c．1032 d．1039
24．a是7×4的二维数组，按行优先方式顺序存储，元素a[0][0]的存储地址为1 000，若每个元素占2个字节，则元素a[3][3]的存储地址为( )
a．1015 b．1016
c．1028 d．1030
25.已知10×12的二维数组a，按“行优先顺序”存储，每个元素占1个存储单元，已知a[1][1]的存储地址为420，则a[5][5]的存储地址为（ ）
a.470 b.471
c.472 d.473
26. 由三个结点可以构造出多少种不同的二叉树( )
a)3b)4
c)5d)6
27. 在一棵深度为k的完全二叉树中，所含结点个数至少( )
a)2kb) 2k+1
c)2k-1d) 2k-1
28. 如图所示的4棵二叉树中，（ 不是完全二叉树。
29. 设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数是( )
a)12b)13c)14d)15
30. 树中所有结点的度等于所有结点数加（ ）
a.0 b.1 c.-1 d.2
31. 在一棵树中，每个结点最多有（ ）个前驱结点。
a.0b.1 c.2d.任意多个。
32. 在一棵具有n个结点的二叉树的第i层上，最多具有（ ）个结点。
a.2i b. 2i+1 c. 2i-1 d. 2n
33. 在一棵二叉树上第5层的结点数最多为（ ）
a.16b.15c.8d.32
34. 下列关于二叉树的说法正确的是( )
a)一颗二叉树中的结点个数大于0
b)二叉树中任何一个结点要么是叶子，要么恰有两个子女。
c)一棵二叉树中叶子结点的个数等于度为2的结点个数加1
d)二叉树中任何一个结点的左子树和右子树上的结点个数一定相等。
35. 在一棵完全二叉树中，若编号从1开始，编号为i的结点存在右孩子，则右孩子结点的编号为（ ）
a.2ib.2i-1c.2i+1 d.2i+2
顺序 （n-1）/2 99和6 n-i+1 xsxxssxxss m-1 栈顶删除
front=(front+1)%m 17 和33 138 2h-1 2k-1和2k-1
二、填空题(每空2分，共30分)
1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用___存储结构。
2．线性表l=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是___
3．设二叉树根结点的层次为0，对含有100个结点的二叉树，可能的最大树深度和最小树深分别是。
4．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动___个元素。
5.用x代表进栈操作，s代表出栈操作。给出利用栈将字符串"a*b-c"改变为"ab*c-"的操作步骤例如：将"abc"改变为"bca",则其操作步骤为xxsxss。
6．顺序栈存放在s[m]中，s[0]为栈底，栈顶指针top初始值为-1，则栈满的条件是top
7.在栈结构中，允许插入和删除的一端称为___
8．队列只能在队尾进行插入操作，在队首进行操作。
9．设循环队列存放在向量data[0..m-l]中，在出队操作后，队头指针front变化为。
10.设循环队列的容量为50(序号从0到49)，现经过一系列的入队和出队运算后，有①front=11，rear=29；②front=29，rear=11；在这两种情况下，循环队列中的元素个数分别是___和___
1期中考试试卷
2014 2015 2期末考试 语文 试题卷。一 现代文阅读 共13分 阅读下面文章，完成1 4题。语文是盐。胡展奋。近来颇听到一些批评当下语文教育模式误人子弟的言论，这原本正常。但渐渐地，有人 特别是一些作家 对语文本身鄙薄不堪，甚而主张 干脆废掉语文课 这，就不正常了。但凡作家做学生的时候，语文...
1期中考试试卷
张掖市职教中心2011 2012学年第一学期。10级 09级 安全与心理 第三次月考试卷。1.中暑者体温过高时，可以用冰袋放在中暑者的等处。2.中暑的急救方法是让病人立即离开转移至处休息，解开衣服，平卧，同时让患者多喝等消暑饮料。3.禁止标志的含义是。4.事故的特点是事故发生原因。5.劳动者每日工作...
1期中考试试卷 1
2010 2011学年第一学期。数学 期中考试试卷。1.下列叙述正确的是 a.空集表示为b.不大于1的实数集是。2.以下关系正确的是 a3.设u a b 则以下关系正确的是 菱形 平行四边形 矩形 正方形 4.设全集u a 则cua是 a.c.5.集合的所有真子集的个数是 a.31b.32 c.28...