作业二。
一、 单项选择题。
1. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是（ c ）。
a. o(1) b. o(n) c. o(n2) d. o(nlog2n)
2. 带表头的双向循环链表的空表满足（ b ）。
a. first＝nullb. first->rlink==first
c. first->llink==null d. first->rlink==null
3. 栈的插入和删除操作在（ a ）进行。
a. 栈顶 b. 栈底 c. 任意位置 d. 指定位置。
4. 在一个顺序存储的循环队列中，队头指针指向队头元素的（ c ）位置。
a. 前一个 b. 后一个 c. 当前 d. 后面。
5. 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（ d ）。
a. front+1 ==rear b. rear+1 ==front c. front ==0 d. front ==rear
6. 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行（ a ）操作。
a. x=top->data; top=top->link; b. top=top->link; x=top->data;
c. x=top; top=top->link; d. x=top->data;
7. 为增加内存空间的利用率和减少溢出的可能性， 由两个栈共享一块连续的内存空间时， 应将两栈的（ d ）分别设在这块内存空间的两端。
a. 长度 b. 深度 c. 栈顶 d. 栈底。
8. 在系统实现递归调用时需利用递归工作记录保存（ c ），当递归调用程序执行结束时通过它将控制转到上层调用程序。
a. 调用地址 b. 递归入口 c. 返回地址 d. 递归出口。
9. 设串s1=’abcdefg’，s2=’pqrst’，函数con (s1,s2)返回s1和s2串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con (subs (s1,2,len (s2)),subs (s1,len (s2),2))的结果串是（ d ）。
a. bcdef b. bcdefg c. bcpqrstd. bcdefef
10. 设有一个广义表a =(a)，其表尾为（ c ）。
a．a b．( c．（）d．(a)
11. 对于一组广义表a( )b(a,b), c(c,(e,f,g)),d(b,a,c), e (b, d)，其中的c是（ c ）。
a. 线性表 b. 纯表 c. 递归表 d. 再入表。
12. 在一棵树中，（ c ）没有前驱结点。（必须是对树做遍历才有前驱后继的说法，所以本题不严密，应该指出是先序遍历树根没有前驱节点。）
a. 树枝结点 b. 叶子结点 c. 树根结点 d. 空结点。
13. 在一棵具有n个结点的二叉树的第i层上(假定根结点为第0层，i大于等于0而小于等于树的高度)，最多具有（ a ）个结点。
a. 2i b. 2i+1 c. 2i-1 d. 2n
二、填空题。
1. 链表与顺序表、索引表、散列表等都是数据逻辑结构的(存储)表示。
2. 队列是一种限定在表的一端插入，在另一端删除的线性表，它又被称为（先进先出）表。
3. 向一个顺序栈插入一个元素时，首先使（栈顶指针）后移一个位置，然后把待插入元素写入到这个位置上。
4. 向一个循环队列中插入元素时，需要首先移动（队尾）指针，然后再向所指位置写入新元素。
5. 在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有（1）个结点。
6. 串abaabbabab的next数组值为（0 1 1 2 2 3 1 2 3 4 ）。
7. 非空广义表的除第一个元素外其他元素组成的表称为广义表的（表尾）。
8. 广义表的深度定义为广义表括号的（重数）。
9. 一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))结点f的层数为（3）。假定树根结点的层数为0。
10. 在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有（6）个。
11．一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为（6）个。
三、判断题（对/错）
1在用单链表表示的链式队列q中，队头指针为q->front，队尾指针为q->rear，则队空条件为q->front ==q->rear。
2递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用本身需要分配额外的空间和传递数据和控制，所以时间与空间开销通常都比较大。
3将f = 1 + 1/2 + 1/3+ …1/n转化为递归函数时，递归部分为f (n) =f (n-1) +1/n，递归结束条件为f (1) =1。
4一个广义表 ( a), b), c), d) )的长度为3，深度为4。
5若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。
6在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。
8在树的存储中，若使每个结点带有指向双亲结点的指针，这为在算法中寻找双亲结点带来方便。
8于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为o(log2n)。
9串既可以采用顺序存储，也可以采用链式存储。
四、运算题。
1. 已知一棵树的静态双亲表示如下，其中用-1表示空指针，树根结点存于0号单元，分别求出该树的叶子结点数、单分支结点数、两分支结点数和三分支结点数。
序号： 0 1 2 3 4 5 6 7 8 9 10
data: a b c d e f g h i j k
parent: -1 0 1 1 3 0 5 6 6 0 9
答：叶子结点数： 5
单分支结点数：3
两分支结点数：2
三分支结点数：1
6. 已知一个图的顶点集v和边集g分别为：
v=;e=;
假定该图采用邻接表表示，每个顶点邻接表中的边结点都是按照终点序号（即数值域的值）从小到大的次序链接的，试写出：
(1) 从顶点1出发进行深度优先搜索所得到的顶点序列；
(2) 从顶点1出发进行广度优先搜索所得到的顶点序列。
答： （1）：1,2,4,5,3,6
五、算法分析题。
1. 请写出下面算法的功能。
void unknown(queue &q)
while(!
答：利用"栈"作为辅助存储，将队列中的元素逆置（即相反次序放置）。
2. 下面是判断一个带表头结点的双向循环链表l其前后结点值是否对称相等的算法， 若相等则返回1，否则返回0。请按标号补充合适的内容。
int symmetry ( doublellist* dl )
else __3)__
return 1;
答：(1) q = q->llink (2) return 1 (3) return 0
3. 设有一个求解汉诺塔（hanoi）的递归算法如下：
void hanoi ( int n, int peg1, int peg2, int peg3 )
当使用hanoi( 3,1,2,3)进行调用时，执行过程中else子句的cout语句得到的结果为：答：1→2
4. 已知二叉树中的结点类型bintreenode定义为：
struct bintreenode ;
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。下面函数的功能是：从二叉树bt中查找值为x的结点，返回指向其父结点的指针。
若该结点不存在或为树根结点则返回空。算法中参数pt的初值为null。请在划有横线的地方填写合适内容。
bintreenode* parentptr(bintreenode* bt, bintreenode* pt, elemtype& x)
if(bt==null) return null;
else if(bt->data==x) return pt;
else 答： (1) return pt
(2) (pt=parentptr(bt->right,bt,x))
(3) return null 或return 0
5.函数strcat(char *s1,char *s2)是将字符串s2连结在字符串s1之后，构成一个首指针为s1的字符串。
void strcat(char *s1,char *s2)
while(*s1!= 0′)
for (;2）;s1++,s2++)
答：（1）s1++
(2) (s1=*s2)!=0'
作业二含答案
作业一姓名。1 一个做直线运动的物体，在t 5s内速度从v0 12m s，增加到 18m s，通过的位移是s 70m，这个物体5s内的平均速度是 a a 14m sb 15m s c 6m sd 无法确定。2 判断下列图像属于匀加速直线运动的是 c abcd 3 下列关于加速度的说法中，正确的是 d...
定义新运算 含答案
七年级奥赛练习题 定义新运算。班级姓名。规定新的代数运算是一类较新颖的数学问题，它是以近世代数为背景的。近年来，多次出现在国内外的数学竞赛题中。解这类问题的关键在于认识新运算的含义。在计算时严格遵照规定的法则代入数值。值得注意的是，这样规定的新运算未必满足通常的结合律及交换律。一 填空题 1 对任意...
高二物理作业一含答案
高二物理作业一 2013 10 28 1.2010 北京高考 用控制变量法，可以研究影响平行板电容器电容的因素 如图3 1 3 设两极板正对面积为s，极板间的距离为d，静电计指针偏角为 实验中，极板所带电荷量不变，若 a 保持s不变，增大d，则 变大 b 保持s不变，增大d，则 变小 c 保持d不变...