2007年山东省专升本考试数据结构真
题
一、判断题（10分。本大题共10小题，每小题1分，在小题左面用√表示是，×表示否）
1. 线性表的顺序存储结构是一种随机存储结构。（）
2. 一个栈的入栈序列是a, b, c, d, e，则dceab是一个不可能的输出序列。（）
3. 广义表(a, (a,b), d, e, ((i, j), k)) 的深度是2。（）
4. 树是一种重要的线性数据结构。（）
5. 按照二叉树的定义，具有三个结点的二叉树有5种。（）
6. 已知一个有向图的邻接矩阵表示，计算第i个结点的出度的方法是求矩阵第i列非零元的个数。（）
7. 将递归算法转换为对应的非递归算法时，通常需要使用队列。（）
8. 在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同。（）
9. 散列法存储的基本思想是由关键字的值决定数据的存储地址。（）
10. （101，88，46，70，34，39，45，58，66，10）是堆。（）
二、填空题（15分。本大题共5小题，5个空，每个空3分，将正确答案填在空格处）。
1. 将下三角矩阵A[1..8, 1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7, 5]的地址为___________。
2. 若某二叉树有20个叶结点，有30个只有一个孩子的结点，则该二叉树的总结点数为___________。
3. 如果以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是___________。
4. 在顺序存储的二叉树中，编号为i和编号为j的结点处在同一层的条件是___________。
5. 有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当折半查找值为82的结点时，___________次比较后查找成功。
三、（10分）已知关键字序列为{46，57，84，32，73，36，15，48，90，20}，要求：（1）构造一棵二叉排序树；
（2）在等概率情况下，该二叉排序树查找成功的平均查找长度。
四、（8分）假设在长度大于1的循环链表中，既无头结点，也无头指针，p为指向该链表中某个结点的指针。设计一个算法，删除p指向结点的前趋结点。
五. （7分）设算术表达式由字符串b表示，其中可以包括三种括号：圆括号、方括号和花括号，嵌套的顺序任意，如{ [ ( ) ] ( ) }是正确的。请编写一个算法，实现判别给定表达式中所含括号是否正确配对。
2007年山东省专升本考试数据结构真题答
案及解析
一、判断题
1.【答案】√
【解析】顺序存储结构的特点：
（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；
（2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。2.【答案】√
【解析】考查堆栈“后进先出”的特点。第一个出栈元素是d，说明a、b、c已经入栈，因为a先于b进栈，所以必定在b之后出栈。
3.【答案】×
【解析】广义表的深度定义为所含括弧的重数，所以深度应为3。
4.【答案】×
【解析】线性表、堆栈、队列都可认为是线性结构，树和二叉树都是树形结构，而图则属于图状结构。
5.【答案】√
【解析】如图所示：
6.【答案】×
【解析】第i列非零元的个数表示的是第i个结点的入度，第i行非零元的个数表示的是第i个结点的出度。
7.【答案】×
【解析】将递归算法转换为对应的非递归算法时，通常需要使用栈。
8.【答案】×
【解析】在哈夫曼编码中，当两个字符出现的频率相同时，权重相同，但这两个字符的位置不同，所以其编码也不同。
9.【答案】×
【解析】散列法存储的基本思想是由关键字的值决定数据的存储地址，也即是把关键字的
值作为自变量，通过一定的函数（称为散列函数）计算出对应的函数值，把这个函数值解释为数据的存储地址，而不是直接把关键字的值作为数据的存储地址。 10.【答案】√ 【解析】是大顶堆。 二、填空题
1.【答案】1100
【解析】对下三角矩阵：（ i>=j ,考虑包括主对角线上的元素） 行优先存储： k ＝ i(i-1)/2 + j - 1 ； 所以地址为：1000+25*4=1100。 2.【答案】69
【解析】n ＝ n 0 ＋ n 1 ＋ n 2
n 0 = n 2 + 1
所以n= 2*n 0+ n 1-1=40+30-1=69 3.【答案】69
【解析】如下图所示，所以结果为：2*（6+7+8）+3*（4+5）=69
6 7 8
4 5
4.【答案】k
k i 221<≤
- k
k j 2
21<≤- 5.【答案】4
【解析】 第一步：
元素下标 1 2 3 4 5 6 7 8 9 10 11 12 13 元素关键字 1 3 9 12 32 41 45 62 75 77 82 95 100
low=1
high=13
mid=7
设low 指向首元素（赋值为1），high 指向尾元素（赋值为13），计算下边中值得： mid ＝ ?(low +high)/2? = 7 则有 R[mid]=R[7]=45 > 82
第二步：由以上判断可知，如果记录中存在82，则一定在R[7]之后（因为R是非递减
有序的）。故修改low和high如下：
high值不变，仍然有high＝13；
low的值修改：使其指向R[7]的后一个元素，即使low＝mid+1 ＝ 8 ;
比较范围缩小至R[8]～R[13]。
元素下标 1 2 3 4 5 6 7 8 9 10 11 12 13
元素关键字 1 3 9 12 32 41 45 62 75 77 82 95 100
mid=10
low=8 high=13 mid ＝?(low +high)/2?= 10
则有R[mid]＝R[10]＝77<82
第三步：由以上判断可知，如果记录中存在82，则一定在R[10]之后（同样因为R是非
递减有序的）。故修改low和high的值如下：
元素下标 1 2 3 4 5 6 7 8 9 10 11 12 13
元素关键字 1 3 9 12 32 41 45 62 75 77 82 95 100
low=11 mid=12 high=13 low的值修改，使其指向R[10]的下一个元素，即low＝mid＋1＝11;
high不变，仍然是13。
mid ＝?(low +high)/2?=12
则有R[mid]＝R[12]＝95。
第四步：由以上判断可知，如果记录中存在82，则一定在R[12]之前（同样因为R是非
递减有序的）。故修改low和high的值如下：
元素下标 1 2 3 4 5 6 7 8 9 10 11 12 13
元素关键字 1 3 9 12 32 41 45 62 75 77 82 95 100
low=11 mid=11 high=11 high的值修改，使其指向R[12]的前一个元素，即high＝mid-1＝11;
low不变，仍然是11。
mid ＝?(low +high)/2?=11
则有R[mid]＝R[11]＝82。查找成功。
三、【答案】
（1）构造过程如下：
46
46
57 46
57 84 46
32 57 84
46
32 57
84
73
46
32 57
84
73
36
46 32
57 84 73
36
15
46
32 57
84
73
36 15 48 46
32
57
84
73
36
15
48 90
46
32
57
84
73
36
15
48
90
20
（2）平均查找长度为：（1+2*2+3*4+4*3）/10=2.9 四、【答案】
已知指向这个结点的指针是p ，那么要删除这个结点的直接前趋结点，就只要找到一个结点，它的指针域是指向p 的直接前趋，然后用后删结点法，将结点p 的直接前趋结点删除即可。 算法如下：
void DeleteNode( ListNode *p)
{//删除单循环链表中指定结点的直接前趋结点 ListNode *s, *q; s=p;
while( s->next->next!=p) s=s->next; //删除结点 q=s->next; s->next=q->next; free(s); //释放空间 }
注意：若单循环链表的长度等于1，则只要把表删空即可。
五、【答案】
算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。
（1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；
（2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；
（3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。
下面是解决这个问题的完整算法。
typedef char StackEntry;
int Check( )
{
STACK S; //定义栈结构S
char ch;
InitStack(&S); //初始化栈S
while ((ch=getchar())!=’\n’) { //以字符序列的形式输入表达式
switch (ch) {
case (ch==‘(’||ch== ‘[’||ch== ‘{’): Push(&S,ch);break; //遇左括号入栈
//在遇到右括号时，分别检测匹配情况
case (ch== ‘)’): if (StackEmpty(S)) retrun FALSE;
else {Pop(&S,&ch);
if (ch!= ‘(’) return FALSE; }
break;
case (ch== ‘]’): if (StackEmpty(S)) retrun FALSE;
else {Pop(&S,&ch);
if (ch!= ‘[’) return FALSE; }
break;
case (ch== ‘}’): if (StackEmpty(S)) retrun FALSE;
else {Pop(&S,&ch);
if (ch!= ‘{’) return FALSE; }
break;
default:break;
}
}
if (StackEmpty(S)) return TRUE;
else return FALSE;
}
2008年山东省专升本考试数据结构真题
一、单项选择题（10分、每题1分）
1、在一个单链表，已知p所指向的是q所指向结点的前驱结点，若在q和p之间插入s所指向的结点，则执行（）
A、s->next=q->next;q->next=s
B、q->next=s->next;s->next=q
C、p->next=s;s->next=q
D、q->next=s;s->next=p
2、串是（）
A、一些符号构成的序列
B、一些字母构成的序列
C、一个以上的字符构成的序列
D、任意有限个字符构成的序列
3、数组A[10][10]的下标下界为1，每个元素占2个字节，存储在起始地址为100的连续内存单元，则元素A[3][8]的地址为（）
A、138
B、154
C、111
D、145
4、已知广义表L=((x,y,z),a,(u,t,w)),则从L中取出原子项y的操作是（）
A、head(tail(head(L)))
B、head(head(tail(tail(tail(L)))))
C、head(tail(tail(tail(tail(L)))))
D、head(tail(tail(head(tail(L)))))
5、已知完全二叉树有80个结点，则整个二叉树有____个度为2的结点。（）
A、39
B、41
C、40
D、38
6、赫夫曼树中度为1的结点个数为（）
A、0
B、1
C、2
D、不确定
7、具有n个顶点的有向完全图，边的总数为（）
A、n
B、n(n-1)
C、n-1
D、n(n-1)/2
8、二分查找法适用于存储结构为____的，且按关键字排好序的线性表。（）
A、顺序存储
B、链接存储
C、顺序存储或链接存储
D、索引存储
9、下列排序算法中，第一趟排序结束后，其最大或最小元素一定在其最终位置上的算法是（）
A、归并排序
B、直接插入排序
C、快速排序
D、起泡排序
10、一个有向无环图的拓扑序列个数是（）
A、1个
B、1个或多个
C、0个
D、多个
二、正误判断题（10分，正确打√，错误打×，每小题1分）
1、链表中结点数据域占的存储空间越多，存储密度越小。（）
2、带头结点和不带头结点的单链表在查找、删除、求长度等操作上无区别。（）
3、如果两个串串长相等且对应字符也相同，则这两个串相等。（）
4、压缩存储的三角矩阵和对称矩阵的存储空间不相同。（）
5、满二叉树是完全二叉树。（）
6、对于给定的树，与其对应的二叉树是唯一的。（）
7、线索二叉树的指针域中，指向前驱或后继的个数少于指向孩子的个数。（）
8、给定图的邻接矩阵存储不一定唯一。（）
9、若一个有向图的邻接矩阵主对角线以下的元素均为0，则该图拓扑有序序列存在。（）
10、对n个记录进行直接插入排序，其平均时间复杂度为O(nlog2n）。（）
三、填空题（10分，1题每空2分，其他题每空1分）
1、下列函数的功能是实现带头结点的单链表逆置。
void turn(slink *L) {
slink *p,*q;
p=_____________________________; L->next=NULL;
while(___________________________) {
q=p;
p=___________________________; q->next=L->next; L->next=q; } }
2、“算法”（Algorithm ）就是对求解问题步骤的一种描述，也称为算法设计。它具有以下五个特征有穷性，_____________,_______________，输入和输出。
3、评价算法好坏的五个方面_______________,_______________,正确性，可读性，健壮性。
四、操作计算题（10分，每题5分）
1、有一组关键字序列（24，19，56，13，97，59，41，85，1，87），写出用堆排序法进行升序排序的初始堆序列及第一趟排序后的堆序列。
2、给定如下图所示的带权无向图G1。
（1）画出该图的邻接矩阵
（2）给出采用普里姆算法从顶点3出发构造最小生成树的的过程。
五、算法设计题（10分）
给定二叉树，采用链式结构存储，编写算法void count(BitTree bt),实现功能：统计二叉树中度为1的结点数目。
1
2 3
4 6
5 9 10
5 11
8 7
7 6
2008年山东省专升本考试数据结构真题答
案及解析
一、单项选择题
1.【答案】C
【解析】p->next表示结点中存放的指针,该指针用来指向某个结点，原来的连接关系是p->next=q，意思是p中存放的指针的值是q，即p指向q。插入的意思,打个比方，原来排队q在p的后面,现在要插一个s在他们中间，需要做的事就是把原来p，q二人的联系转化为p，s，q三人的联系，先让p指向s，即p->next=s；然后让s指向q，即s->next=q。
2.【答案】D
【解析】串是由零个或多个字符组成的有限序列，一般记为：s = ‘a1a2…an’ (n>=0) 。零个字符的串称为空串，n为串的长度。串的元素ai可以是字母、数字或其他字符。
3.【答案】B
【解析】数组元素A[i,j]的地址为：Loc(A[i,j]) = L1 + (i-1)×U2×d ＋（j－1）×d。
4.【答案】A
【解析】L=((x,y,z),a,(u,t,w))，head(L)= (x,y,z)，tail(head(L))= (y,z)，head(tail(head(L)))=y。
5.【答案】A
【解析】n ＝n0＋n1＋n2
n0 = n2 + 1
n＝n1 +2n2＋1
n=80，为完全二叉树，说明度为1的结点只有1个，所以n2=39。
6.【答案】A
【解析】构造Huffman树的步骤：
①对给定的n个权值按照非递减顺序排列，构造n棵只有一个结点的二叉树的集合F ＝｛T1,T2,…Tn｝；
②在F中选定两棵根结点的权值最小的两个二叉树作为左右子树，构造一棵新的二叉树，新的二叉树的根结点的权值设为其左右子树根结点的权值之和；
③从F中删除原来的两棵二叉树，同时将新二叉树插入其中；
④重复执行（2）和（3），直到F中剩余一棵二叉树，这棵树就是所求的Huffman树，结束。
根据构造步骤可知，Huffman树中只有度为0的叶子结点和度为2的新生成结点。
7.【答案】B
【解析】有向图G中弧数目的取值范围：0<= e <= n(n-1)。有n(n-1)条弧的有向图称为有向完全图。
8.【答案】A
【解析】折半查找（二分查找法）要求查找表用顺序存储结构存放且各数据元素按关键字有序（升序或降序）排列，也就是说折半查找只适用于对有序顺序表进行查找。有序顺序表
也称为有序表。
9.【答案】D
【解析】起泡排序是交换排序中一种简单的排序方法。它的基本思想是对所有相邻记录的关键字值进行比效，如果是逆序（a[j]>a[j+1]），则将其交换，最终达到有序化。其处理过程为：
1> 将整个待排序的记录序列划分成有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录。
2> 对无序区从前向后依次将相邻记录的关键字进行比较，若逆序则将其交换，从而使得关键字值小的记录向上“飘浮”（左移），关键字值大的记录好像石块，向下“堕落”（右移）。每经过一趟冒泡排序，都使无序区中关键字值最大的记录进入有序区，对于由n个记录组成的记录序列，最多经过n-1趟冒泡排序，就可以将这n个记录重新按关键字顺序排列。10.【答案】B
【解析】一个无环的有向图称做有向无环图（directed acycline praph）。简称DAG图。有向无环图是描述含有公共子式的表达式的有效工具。有向无环图的拓扑序列至少一个。
二、正误判断题
1.【答案】×
【解析】存储密度=数据域占的存储空间/整个结点占的存储空间。
2.【答案】×
【解析】单链表在保存时，一般在第一个结点之前辅设一个结点，称为头结点。头结点的数据域可以不存任何信息，也可以存储线性表的长度等附加信息，其指针域中存储指向第一个结点的指针（即第一个元素结点的存储位置）。故单链表的头指针指向头结点，如果头结点的指针域为空，则说明是空表。为了在第一个数据元素前面加入新元素或者删除第一个节点时头指针的值不变，在第一个数据元素前面要加一个所谓的头节点。
3.【答案】√
【解析】两个串相等的充要条件：两个串的长度相等，并且各个对应位置的字符都相等。
4.【答案】×
【解析】上、下三角矩阵元素个数为：1＋2＋3＋…＋n ＝n(n+1)/2。因为取值为0的元素不必保存，则可用一个B[n(n+1)/2]的一维数组来保存上、下三角矩阵的非零值。
n阶对称方阵A中的元素满足下述条件：aij＝aji（1<=i,j<=n）。对称矩阵（方阵）中的每一对数据元素可以共用一个存储空间，因此可以将n2个元素压缩存储到n(n+1)/2个元的空间中，所以存储空间相同。
5.【答案】√
【解析】①满二叉树：一棵深度为k，结点个数为2k-1的二叉树称为满二叉树。满二叉树是深度为k的结点数目最多的二叉树。
②完全二叉树：深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树一一对应时，称为完全二叉树。深度为k的完全二叉树结点个数范围：最小结点数：2k-1，最大结点数2k-1。
满二叉树一定是完全二叉树。 6.【答案】√
【解析】将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。一棵树转换成二叉树后，根结点没有右孩子。 7.【答案】×
【解析】二叉树的二叉链表表示法有n+1个空链。同时，二叉链表（或三叉链表）虽然能方便的找到当前结点的双亲结点或左、右子结点，但如果要求寻找当前结点的前驱结点或者后继结点（按照某种遍历方法），则上述方法就不方便了，只能在遍历过程中动态得到。如将二叉链表法中的n+1个空链利用起来，让其指向当前结点的前驱结点（如果指向左子树的指针域为空）或后继结点（如果指向右子树的指针域为空），则可解决以上问题，这就是线索二叉树提出的原因。 指向孩子的指针个数为n-1。
8.【答案】×
【解析】邻接矩阵法是图的一种顺序存储结构。设G 有n 个顶点，则可用n*n 矩阵A （称为G 的邻接矩阵，行标从1..n ，列标从1..n ）保存该有向图。
对无向图：如果v i ，v j 之间有边，则A 的元素a ij ＝a ji ＝1，否则a ij ＝a ji ＝0；A 为对称矩阵。
对有向图：如果vi 有指向vj 的弧，则A 的元素a ij ＝1，否则a ij ＝0。 对带权图：如果v i ，v j 之间有边或者弧（v i 指向v j ），则A 的元素a ij ＝w ij ，否则a ij ＝INFINITY 。
利用邻接矩阵，可以判断任意两顶点之间是否有边（弧），并可方便求各顶点的度，图的边数等。例如：
对无向图：顶点v i 的度TD(vi)是A 中第i 行（或者第i 列）的元素之和。
对有向图：顶点v i 的出度OD(v i )是第i 行的的元素之和，入度ID(v i )第i 列的元素之和。 对带权图：顶点v i 的度的求法同上类似，但不再是求和，而是求行、列中不为零的元素个数。
9.【答案】√
【解析】矩阵主对角线以下的元素全部为0，即满足如下条件的矩阵。
aij = 0 , i >=j
如下图：
100011001110
该图为有向无环图，所以拓扑有序序列存在。 10.【答案】× 【解析】
排序方法 平均时间
稳定性 直接插入排序 O （n 2
） 稳定 折半插入排序 O （n 2） 稳定 起泡排序 O （n 2） 稳定 直接选择排序 O （n 2）
不稳定
希尔排序 O （n 1.3） 不稳定 快速排序 O （nlog 2n ） 不稳定 堆排序 O （nlog 2n ） 不稳定 2-路归并排序 O （nlog 2n ）
稳定
基数排序
O(d*(rd+n)) 稳定
三、填空题
1.【答案】p=L->next p!=null p=p->next
【解析】逆置时需将每一个结点的指针域作以修改，使其原前趋结点成为后继。 2.【答案】确定性 可行性 3.【答案】时间效率 空间效率 四、操作计算题 1.【答案】
(1)建小堆
85
1
87 13 97
59
41
19 56
24
85 61
97 19 87
59 56
13
41
1
所以初始堆序列为：（1，13，41，19，87，59，56，85，61，97） (2)第一趟排序后的堆序列
85 97
1 61 87
59 56
19
41
13
85
61
97 19 87
59 56
13 41
1
第一趟排序后的堆序列为：（1，13，19，41，61，87，59，56，85，97） 2.【答案】
(1)
0910000 907500 1070067 0500118 0061108 007080??????????????????
(2)
1 3
2 6
3
5
3 7
6
3
5
4
5
5
6
1
2 3
4 6
5
9 10
5
11 8
7
7
6
7
6
3
5
6
2
7
7
6
3
5
6
2
7
4
5
7
6
3
5
6
2
7
4
9
1
6
说明：第三步答案不唯一。
五、算法设计题
void count(BitTree bt)
{
int i=0;
if(bt==NULL)
break;
else if(bt->lchild=0&& bt->rchild!=0|| bt->lchild!=0&& bt->rchild=0) i++;
else
{
i+=count(bt->lchild); i+=count(bt->rchild);
}
printf(“%d”,i);
}
2009年山东省专升本考试数据结构真题
一、填空题（10分，每空0.5分）
1、根据数据元素之间关系的不同，数据的逻辑结构划分为______、______、______、
______。
2、栈是一种特殊的线性表，它允许在表的一端进行____________操作，栈中元素的进
出原则为__________________。
3、深度为k的二叉树其结点数最多有______个结点。
4、通常象交通、道路问题的数学模型是一种称为____________的数据结构。
5、算法的五个重要的特征是______、______、______、______、______。
6、两个字符串相等的充分必要条件是____________________________________。
7、在一棵二叉树中，度为零的结点个数为n，度为2的结点个数为n，则有n=______。
8、树的度是指__________________________________________的最大值。
9、在一个有向图中，某个结点的度是指该结点的______和______之和。
10、在线性表的二分查找法中要求线性表的存储结构必须是采用____________，且表中的元素必须是____________。
二、选择题（10分，每题1分）
1.一个具有10个顶点的无向完全图应有______条边。( )
A. 9
B. 45
C. 55
D. 90
2.长度为n（1…n）的顺序循环队列中，front和rear分别指示队首和对尾，判断队列为满
队列的条件是( )
A. rear=front
B. (rear+1)%n=front
C. rear=0
D. front=0
3.由______组成的集合是一个数据对象。( )
A. 不同类型的数据项
B. 不同类型的数据元素
C. 相同类型的数据项
D. 相同类型的数据元素
4.______是表示线性数据结构的。( )
A. 循环链表
B. 邻接多重表
C. 孩子链表
D. 单链表
5.设一个栈的入栈元素序列为a，b，c，d，e，则不可得到出栈的元素序列有( )。
A. edcba
B. decba
C. dceab
D. abcde
6.______又是一棵满二叉树。( )
A. 二叉排序树
B. 深度为5有31个结点的二叉树
C. 有15个结点的完全二叉树
D. 哈夫曼（Huffman）树
7.折半查找有序表（2，5，8，20，25，36，40，60），若查找元素60，需依次与表中元素
______进行比较。( )
A. 20，36，40，60
B. 25，40
C. 25，40，60
D. 20，36，40
8.查找哈希（Hash）表，解决冲突的方法有( )。
A. 链地址法
B. 线性探测再散列法
C. 直接地址法
D. 除留余数法
9.一个排序算法时间复杂度的大小______有关。( )
A. 不与所需移动记录的数目
B. 与该算法的稳定性
C. 与所需比较关键字的次数
D. 与所需辅助存储空间的大小
10.数据的基本单位是。( )
A. 结点
B. 数据元素
C. 数据类型
D. 数据项
三、求解下列问题（10分，每题5分）
1. 将下面的一个普通书转换成一棵二叉树，并写出它先序、中序、后序三种遍历的遍历序列。
转换后的二叉树：
A
B G H
C D E
F I K
J L M
先序遍历序列：
中序遍历序列：
后序遍历序列：
2. 用克鲁斯卡尔算法将下面的图构造成最小生成树，画出生成过程。
0152
3
4
5636625
5
14
四、程序填空（10分，每空1分） 1.将下面折半查找算法补充完整
算法说明：已知r[1…n]是n 个记录的递增有序表，用折半查找法查找关键字为k 的记录，若查找失败返回零；否则返回该记录的序号值。查找表顺序存储结构定义如下：
#define MAXSIZE
100
typedef struct
{
keytype key;
}Nodetype;
typedef Nodetype Sqlist[MAXSIZE];
算法（C函数）：
int binsearch (Sqlist r, datatype k, int n)
{
int low = 1, high = n, mid;
while (_______________)
{
_______________;
if (r[mid].key= =k)
_______________;
else if (r[mid].key>k)
_______________
else
_______________
}
return (0);
}
2. 将下面单链表的插入算法补充完整。
算法说明：在带有头结点的单链线性表中第i个位置之前插入元素x : typedef _______________
{
DataType data;
struct node *next;
}LNode, *LinkList;
int listinsert (LinkList head, int i, DataType x)
{
LinkList p = head.s
int j = 0;
while (p!=NULL&&j { _______________; j++; } if (p= = NULL) return (0); s = _______________malloc (sizeof (LNode) ); s->data = x; _______________; _______________; return (1); } 五、算法设计（10分） 已知S为顺序栈。写出S的存储结构类型描述。编写算法实现将元素x入栈操作Push (S, x)，入栈成功返回1，否则返回0和删除栈顶元素的出栈操作Pop (S) 出栈成功返回1，否则返回0。 (A )数据的逻辑结构 (B )数据的存储结构 《数据结构》专升本考试试题 (2015 年 3 月) (C )数据的逻辑结构和存储结构 12.算法分析的两个主要方面是( (A )空间复杂度和时间复杂度 (C )可读性和文档性 (D )数据的逻辑结构、存储结构及其基本操作 )o (B )正确性和简单性 (D )数据复杂性和程序复杂性 一、单项选择题(本大题共 20小题，每小题2分，共40分) 1 ?对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为( (A) 正确性 (B) 可行性 ( C) 健壮性 2 ?设S 为C 语言的语句,计算机执行下面算法时， for(i=n-1 ； i>=0 ； i--) for(j=0 ; jn ext==head (B ) p-> next==NULL (C ) p==NULL (D ) p==head 16. 一个栈的输入序列为： a ，b ，c ，d ，e ，则栈的不可能输出的序列是( )o (A ) a,b,c,d,e (B ) d,e,c,b,a (C ) d,c,e,a,b (D ) e,d,c,b,a 17.设SUBSTR(S,i,k)是求S 中从第i 个字符开始的连续k 个字符组成的子串的操作，则对 5 ?深度为k 的完全二叉树，其叶子结点必在第( (A ) k-1 (B ) k (C ) k-1 和 k (D ) 6?具有60个结点的二叉树，其叶子结点有12个， (A ) 11 ( B ) 13 (C ) 48 ( D 37 利于删除操作 利于随机访问 )层上。 1至k 则度为1的结点数为( 7.图的Depth-First Search(DFS) 遍历思想实际上是二叉树( (A )先序 (B )中序 (C )后序 (D )层序 8 .在下列链队列Q 中，元素a 出队的操作序列为( )遍历方法的推广。 S= ' Beijing&Nanjing '，SUBSTR(S,4,5)=( ) (A )‘iji ng ' (B )' jing& ' (C )' ingNa ' (D ) 'ing&N ' 18.广义表((a),a) 的表尾是( )o (A ) a (B ) (a) (C )() (D ) ((a)) 19. 在一棵具有5层的满二叉树中结点总数为( )o (A ) 31 (B ) 32 (C ) 33 (D ) 16 20. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是( )o (A )完全图 (B )连通图 (C )有回路 (D ) —棵树 二、填空题(本大题共20个空，每空2分，共40分) Q (A ) (B ) (C ) (D ) p=Q.fr ont->n ext; p->n ext= Q.front->n ext; p=Q.fr ont->n ext; Q.front->n ext=p->n ext; p=Q.rear- >n ext; p->n ext= Q.rear- >n ext; p=Q->n ext; Q->n ext=p->n ext; 1 .逻辑结构决定了算法的 ____________ ，而存储结构决定了算法的 _____________ o 2. _______________________ 栈和队列都是一种 ______________________ 的线性表，栈 和删除只能在 ______________ 进行。 3. 线性表(a 1,a 2,…,a n )的顺序存储结构中，设每个单元的长度为L,元素a i 的存储地址LOC 4. 已知一双向链表如下(指针域名为next 和prior): 9. Huffman 树的带权路径长度WP 等于( (A )除根结点之外的所有结点权值之和 (C )各叶子结点的带权路径长度之和 )域存储后继结点的地址。 (C ) rchild (D ) root )o 10?线索二叉链表是利用( (A ) Ichild (B ) data 11 ?研究数据结构就是研究( (B ) (D ) ) 所有结点权值之和 根结点的值 现将p 所指的结点插入到x 和y 结点之间，其操作步骤为： ________________________ 5 . n 个结点无向完全图的的边数为 ________________________ ， n 个结点的生成树的边 为 ____________________ o 专升本《结构力学》 一、（共75题,共150分） 1. 图示梁剪力等于零的截面位置x距A点之值为( )。 （2分） 6 5 7 6 .标准答案：D 2. 下列剪力图和弯矩图中的错误为( )。 （2分） A.梁(A)图C截面剪力应连续，C截面弯矩应有突变；图 B.梁C截面弯矩应连续B.图(A)梁B截面剪力不应为零，A截面弯矩不应为零；图B.梁C截面剪力应有突变，C 截面弯矩应光滑连续 C.图(A)梁B截面剪力应为零，弯矩不为零；图段剪力应为曲线，弯矩图在AC 段有极值点 D.图(A)梁剪力在C截面应连续，弯矩在AC段的凹向应一至，图B.梁弯矩在C截面应连续 .标准答案：A 3. 梁在集中力作用的截面处，它的内力图为( )。（2分） 图有突变，M 图光滑连续图有突变，M 图有转折 图有突变，Q 图光滑连续图有突变，Q 图有转折 .标准答案：B 4. 梁的剪力图和弯矩图如图所示，则梁上的荷载为( )。 （2分） 段无荷载，B 截面有集中力 段有集中力，BC 段有均布力 段有均布力，B 截面有集中力偶段有均布力，A 截面有集中力偶 .标准答案：D 5. 用力矩分配法计算弹性结构时,放松结点的顺序________: （2分） A.对计算过程无影响,但对结果有影响; B.对计算过程有影响,但对结果无影响 C.对计算结果和过程均有影响; D.对计算结果和过程均无影响. .标准答案：B 6. 图示结构超静定次数为________: （2分） .标准答案：C 7. 图示结构截面K的轴力值N k为________: （2分） A. B. C. D. .标准答案：C 8. 用几何组成规则分析图示体系是:________ : （2分） A.无多余约束的几何不变体系； B.有多余约束的几何不变体系； C.可变体系； D.瞬变体系。 .标准答案：A 9. 等截面直杆AB的A端的转动刚度S AB________: （2分）A.仅与杆件的线刚度有关; B.仅与杆两端的支承情况有关; C.与杆件的线刚度及荷载情况有关; D.与杆件的线刚度及两端支承情况有关. .标准答案：D 10. 悬臂梁受载如图，弯矩图有三种答案:图A.图B.、和图C.。其中 正确的为( )。（2分） A. .标准答案：C 11. 梁在集中力偶作用的截面处，它的内力图为( )。（2分） 图有突变，M 图无变化 图有突变，M 图有转折 山东:07年专升本考试数据结构模拟试题1 一、填空题:(每小题2分,共10分 1. 设有数据结构(D,R,其中 D 是数据元素的有限集,R 是的有限集。 2. 深度为 k 的二叉树其结点数至多有个。 3. 栈是一种特殊的线性表,它允许在表的一端进行操作。 4. 通常象交通、道路问题的数学模型是一种称为的数据结构。 5. 哈希表是一种查找表,可以根据哈希函数直接获得。 二、单项选择题:(每小题2分,共10分 对于下列各题,在备选答案中选出一个正确的,并将其编号填在“”位置上。 1. 若线性表最常用的操作是存取第 i 个元素及其前驱元素的值,则采用存储方式最节省运算时间。 A. 单链表 B. 双链表 C. 单循环链表 D. 顺序表 2. 下列排序算法中,算法在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。。 A. 直选择排序 B. 冒泡排序 C. 归并排序 D. 堆排序 3. 队列的操作原则是。 A. 先进后出 B. 先进先出 C. 只能进行插入 D. 只能进行删除 4. 在具有 n 个结点的二叉链表中,非空的链域个数为。 A. n-1 B. n C. n+1 D. 不确定 5. 对具有 n 个元素的有序查找表采用折半查找算法查找一个键值,其最坏比较次数的数量级为。 A. O(log2n B. O(n C. O(nlog2n D. O(n2 三、判断题:(每小题2分,共10分 判断下列各题是否正确,若正确,在题后的括号内填“T”,否则填“F”。 1. 在栈为空的情况下不能作出栈处理,否则,将产生下溢出。( 2. 如果有向图 G=(V, E 的拓扑序列唯一,则图中必定仅有一个顶点的入度为0、一个顶点的出度为0。( 3. 在大根堆中,必定满足每个结点的键值大于其左右子树中所有结点的键值。( 4. 在采用线性探测法处理冲突的散列表中所有同义词在表中相邻。( 5. 在索引顺序表中,对索引表既可采用顺序查找,也可采用二分查找。( 四、解答下列各题:(每题10分,共40分 1. 已知线性表 L 采用带头结点的的单向循环链表表示,试给出它的存储结构类型描述及相应的示意图。。 2. 已知一棵二叉树的先序、中序和后序序列如下所示,请填写各序列中空格处的结点,并画出该二叉树的二叉链表存储结构示意图。 先序序列是:_ B _ F _ I C E H _ G;中序序列是:D _ K F I A _ E J C _ ; 后序序列是:_ K _ F B H J _ G _ A 3. 已知数据表为(48,70,33,65,24,56,12,92,86,22,a 写出采用快速排序算法进行排序时第一趟快速划分的详细过程及结果;b 写出按基数排序思想对最低位进行一次分配和收集的结果。 4. 对图1所示的带权无向图,写出它的邻接矩阵和深度优先搜索序列,并按克鲁斯卡算法求其最小生成树(写出求解的详细过程示意图。 图1 带权无向图 五、算法设计题:(前两题必做,每题15分,共30分;第三题为附加题,选做,10分 作业题（一） 一、单项选择题 1. 从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 2. 链表不具有的特点是（） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 3.下面程序段的时间复杂度的量级为（）。 For(i=1;i<=n;i++) For(j=1;j<=I;j++) For(k=1;k<=j;k++) X=x+1; A．O(1) B．O(n) C．O(n2) D．O(n3) 4.在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。 A．2 B．3 C．4 D．6 5、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（）。 A．98 B．100 C．102 D．106 6、判定一个栈s（最多元素为m0）为空的条件是（）。 A．s-〉top! =0 B．s-〉top= =0 C．s-〉top! =m0 D．s-〉top= =m0 7、循环队列用数组A[m]（下标从0到m-1）存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）。 A．（rear-front+m）%m B．rear-front+1 C．rear-front-1 D．rear-front 8、设有两个串S1与S2，求串S2在S1中首次出现位置的运算称作（）。 A．连接B．求子串 C．模式匹配D．判子串 9、设串S1='ABCDEFG'，S2='PQRST'，函数con（x，y）返回x和y串的连接串，subs(s,i,j)返回串S的的从序号i的字符开始的j个字符组成的子串，len(s)返回串S的长度，则con(subs(S1,2,len(S2)),subs(S1,len(S2),2))的结果是（）。 专升本《工程力学》 一、（共75题,共150分） 1. 关于力对轴的矩，下列说法错误的是（）。（2分） A.力与轴相交，力对轴无矩 B.力与轴平行，力对轴无矩 C.力与轴共面，力对轴无矩 D.力与轴交叉，力对轴无矩 .标准答案：B,C 2. 下列结论哪些是正确的__________: （2分） A.构件的强度表示构件抵抗破坏的能力， B.构件的刚度表示构件抵抗变形的能力， C.构件的稳定性表示构件维持其原有平衡形式的能力， D.构件的强度、刚度和稳定性愈高愈好。 .标准答案：A,B,C 3. 图示A、B两物体，自重不计，分别以光滑面相靠或用铰链C相联接，受两等值、反向且共线的力F1、F2的作用。以下四种由A、B所组成的系统中，哪些是平衡的？( )。 （2分） A. .标准答案：B,D 4. 以下四种说法，哪一种是错误的( )。（2分） A.力在平面内的投影是个矢量； B.力对轴之矩等于力对任一点之矩的矢量在该轴上的投影； C.力在平面内的投影是个代数量； D.力偶对任一点O之矩与该点在空间的位置有关。 .标准答案：B,C,D 5. 下列说法正确的是( ) （2分） A.理论力学中我们把所有的物体都抽象化为变形体。 B.在理论力学中我们把所有的物体都抽象化为刚体。 C.稳定性是指结构或构件保持原有平衡状态。 D.理论力学是在塑性范围内，大变形情况下研究其承截能力。 .标准答案：C 6. 三力平衡定理是( )。（2分） A.共面不平行的三个力相互平衡必汇交于一点； B.共面三力若平衡，必汇交于一点； C.三力汇交于一点，则这三个力必互相平衡。 .标准答案：A 7. 图示系统只受F=10KN作用而平衡，L=10m,C截面的弯矩应为( )。 题3图（2分） A.10KN.m； B.20KN.m； C.-5KN.m； D.25KN.m；。 .标准答案：D 8. 将受扭空心圆轴的内、外直径均缩小为原尺寸的一半，则该轴的最大剪应力是原来的（）倍。（2分） A.2 B.4 C.8 D.16 .标准答案：C 9. 两根截面面积相等但截面形状和材料不同的拉杆受同样大小的轴向拉力，它们的应力是否相等？（）（2分） 《数据结构》专升本考试试题 (2015年3月) 一、单项选择题(本大题共20小题,每小题2分,共40分) 1.对于一个算法,当输入非法数据时,也要能作出相应的处理,这种要求称为( )。 (A) 正确性 (B) 可行性 (C) 健壮性 (D) 输入性 2.设S为C语言的语句,计算机执行下面算法时,算法的时间复杂度为( )。 for(i=n-1;i>=0;i--) for(j=0;j 结构力学专升本作业题参考答案 一、选择题 1、图示结构中，A 支座的反力矩A M 为（ ）。 A. 0 B. 1kN.m （右侧受拉） C. 2kN.m （右侧受拉） D. 1kN.m （左侧受拉） 答案：C 2、图示组合结构中，杆1的轴力1N F 为（ ）。 A. 0 B. 2 ql - C. ql - D. q 2- q 答案：B 3、图示结构的超静定次数为（ ）。 A. 1 B. 5 C. 6 D. 7 答案：D 4、图示对称结构的半边结构应为（ ）。 答案：A 5、图示结构中， BA M（设左侧受拉为正）为（）。 A. a F P 2 B. a F P C. a F P 3 D. a F P 3 - 答案：C 6、图示桁架中，B支座的反力 HB F等于（）。 A. 0 B. P F 3 - C. P F 5.3 D. P F 5 答案：D 7、图示结构的超静定次数为（）。 A. 1 B. 3 C. 4 D. 5 答案：B 8、图示对称结构的半边结构应为（ ）。 答案：C 二、填空题 1、图示桁架中，有 根零杆。 答案：10 2、图示为虚设的力状态，用于求C 、D 两结点间的 。 答案：相对水平位移 3、超静定刚架结构在荷载作用下采用力法求解时，当各杆EI 值增加到原来的n 倍时，则力法方程中的系数和自由项变为原来的 倍；各杆的内力变为原来的 倍。 答案： n 1 ；1 4、写出下列条件下，等截面直杆传递系数的数值：远端固定=C ，远端铰支=C ，远端滑动 =C 。 答案：2/1；0；1- 5、图示桁架中，有 根零杆。 专升本《数据结构》 一、（共75题,共150分） 1. 数据的基本单位是（）。（2分） A.数据元素 B.记录 C.数据对象 D.数据项 .标准答案：A 2. （）是数据的不可分割的最小单位。（2分） A.数据对象 B.数据元素 C.数据类型 D.数据项 .标准答案：D 3. 算法的空间复杂度是对算法（）的度量。（2分） A.时间效率 B.空间效率 C.可读性 D.健壮性 .标准答案：B 4. （）是限制了数据元素的内部结构仅为一个字符的线性表。（2分） A.栈 B.队列 C.串 D.数组 .标准答案：B 5. 串的长度是指串中所含（）的个数。（2分） A.不同字符 B.不同字母 C.相同字符 D.所有字符 .标准答案：D 6. 采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次。（2分） A.1 B.2 C.3 D.4 .标准答案：B 7. 线性表的顺序存储结构是一种（）的存储结构。（2分） A.顺序存取 B.随机存取 C.索引存取 D.Hash存取 .标准答案：B 8. 数组a[1..m]采用顺序存储，a[1]和a[m]地址分别为1024和1150，每个元素占2字节，则m是（）。（2分） A.64 B.32 C.16 D.8 .标准答案：A 9. 深度为h的二叉树，第h层最多有（）个结点。（2分） A.h B.2h-1 C.2h-1 D.2h .标准答案：C 10. m个结点的二叉树，其对应的二叉链表共有（）个非空链域。（2分） A.m B.m+1 C.2m D.m-1 .标准答案：B 11. 下面叙述错误的是（）。（2分） A.顺序表是借助物理单元相邻表示数据元素之间的逻辑关系 B.对于空队列进行出队操作过程中发生下溢现象 C.有向图的邻接矩阵一定是对称的 D.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的 .标准答案：C 12. 以下与数据的存储结构无关的术语是（）。（2分） A.循环队列 B.双向链表 C.哈希表 D.数组 .标准答案：D 13. 在一个长度为n的链式栈中出栈实现算法的时间复杂度为（）。（2分） A.O(1) B.O(log n) C.O(n) D.O(n2) .标准答案：A 14. 在具有k个度数为2的二叉树中，必有（）个叶子结点。（2分） A.k B.k-1 C.2k D.k+1 .标准答案：D 15. 在关键字序列（10,20,30,40,50）中，采用折半法查找20，关键字之间比较需要（）次。（2分） A.1 B.2 C.3 D.4 .标准答案：C 16. 16某二叉树的后序遍历序列和和中序遍历序列均为abcd，该二叉树的前序遍历序列是（）。（2分） A.abcd B.dcba C.acbd D.dbca .标准答案：B 17. n个顶点的无向连通图的生成树，至少有（）个边。（2分） A.n(n-1) B.n(n-1)/2 C.2n D.n-1 .标准答案：D 18. 可以采用（）这种数据结构，实现二叉树的层次遍历运算。（2分） A.队列 B.树 C.栈 D.集合 .标准答案：A [试题分类]:专升本《结构力学》_08002650 [题型]:单选 [分数]:2 1. 图（a）所示超静定结构用力法求解时，基本未知量为（）. A.3个 B.10个 C.2个 D.3个 答案:C 2.轴力图应画在（） A.结构的受拉边 B.结构的任意边，不要标正负号 C.结构的任意边，但要标正负号 D.结构的上边，不要标正负号 答案:C 3. 图示体系有几个多余约束？ A.3个 B.5个 C.6个 D.1个 答案:B 4. 图示结构截面K 的轴力值Nk为________: A. B. C. D. 答案:D 5. 悬臂梁受载如图，弯矩图有三种答案:图 A.图 B.、和图 C.。其中正确的为()。 A.见图 B.见图 C.见图 D.见图 答案:B 6. 图示体系有几个多余约束？ A.5个 B.3个 C.6个 D.1个 7 12 q l 2 q l - 2 q 12 q l - 答案:B 7.下列说法中，哪个说法正确?() A.位移法的基本结构是超静定梁 B.力法的基本结构是超静定刚架 C.力法的基本方程是平衡方程 D.力法和位移法的基本未知量相同 答案:A 8. 图示结构的内力图是（） A.M图、Q图均不正确 B.M图不正确、Q图为正确 C.M图、Q图均正确 D.M图正确、Q图不正确 答案:A 9. 图示桁架结构的是（） A.简单桁架结构 B.复杂桁架结构 C.组合桁架结构 D.不是桁架结构 答案:A 10.力法典型方程的物理意义是() A.结构的变形协调条件 B.结点的平衡条件 C.结构的平衡条件 D.结构的平衡条件及变形协调条件 答案:A 11.位移法的基本未知数是() A.结构上所有结点的角位移和线位移 B.结构上所有结点的独立角位移和独立线位移 第一章英语；英语整体上看试卷一共分为六道大题，一是单项选择题；试题分析；一单项选择：20’；ishelpfulinlookingforajo；A.certificateB.grad eC.re；A.senseB.savingC.imforma；A.momentB.pointC.heartD.；4.Mymebysa yingthatIcould；A.discou 第一章英语 英语整体上看试卷一共分为六道大题，一是单项选择题共计20道20分；二是完型填空10道10分；三是阅读，分三个篇章，每个篇章5道选择，各2分，总计30分；四是用词的适当形式填空，10道10分；五是翻译(汉译英)，5道2 0分；六是写作10分；总计100分。 试题分析 一单项选择：20’ is helpful in looking for a job，but it doesn’t mean a job. A.certificate B.grade C.record D.debt A.sense B.saving C.imformation https://www.doczj.com/doc/cb8175328.html,fort A.moment B.point C.heart D.face 4.My me by saying that I could win in the speech contest ,so I to ok part in it. A.discouraged B.encouraged C.courage D.asked 5.His new book to the top as the bestseller. A.rocketed B.raised C.stayed D.reached 6.The president was invited to address the audience at the openin g Of the Olympic Games. A.ceremony B.speech C.meeting D.celebration 7.In some western is that blank cats will bring misforture to peo ple. A.superstar B.superpower C.superstitious D.superstition 8.The the cup from the table with any guest’s knowledge . A.reminded B.reduced C.refused D.removed A.looks B.sets C.symbolizes D.Seeks 10.Although we are of the same age,we height and weight. 11.Some soldiers are very his orders strictly. A.loyalty B.loyal C.faithfulness D.faith （损坏）. A.What B.whatever C.who D.whoever 13.All of those the peace conference were asked to sign their nam es on piece of cloth. A.attended B.preseted C.went D. was 专升本《数据结构》模拟题试卷 一. （共75题,共150分） 1. 数据的基本单位是（）。（2分） A.数据元素 B.记录 C.数据对象 D.数据项 ★检查答案标准答案：A 2. （）是数据的不可分割的最小单位。（2分） A.数据对象 B.数据元素 C.数据类型 D.数据项 ★检查答案标准答案：D 3. 算法的空间复杂度是对算法（）的度量。（2分） A.时间效率 B.空间效率 C.可读性 D.健壮性 ★检查答案标准答案：B 4. （）是限制了数据元素的内部结构仅为一个字符的线性表。（2分） A.栈 B.队列 C.串 D.数组 ★检查答案标准答案：B 5. 串的长度是指串中所含（）的个数。（2分） A.不同字符 B.不同字母 C.相同字符 D.所有字符 ★检查答案标准答案：D 6. 采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次。（2 分） A.1 B.2 C.3 D.4 ★检查答案标准答案：B 7. 线性表的顺序存储结构是一种（）的存储结构。（2分） A.顺序存取 B.随机存取 C.索引存取 D.Hash存取 ★检查答案标准答案：B 8. 数组a[1..m]采用顺序存储，a[1]和a[m]地址分别为1024和1150，每个元素占2字节，则m是（）。（2分） A.64 B.32 C.16 D.8 ★检查答案标准答案：A 9. 深度为h的二叉树，第h层最多有（）个结点。（2分） A.h B.2h-1 C.2h-1 D.2h ★检查答案标准答案：C 10. m个结点的二叉树，其对应的二叉链表共有（）个非空链域。（2分） A.m B.m+1 C.2m D.m-1 ★检查答案标准答案：B 11. 下面叙述错误的是（）。（2分） A.顺序表是借助物理单元相邻表示数据元素之间的逻辑关系 B.对于空队列进行出队操作过程中发生下溢现象 韩山师范学院2013年专升本插班生考试试卷 计算机科学与技术 专业 数据结构 试卷 （A 卷） 一、 单项选择题（每题2分，共40分） 1、从逻辑上可以把数据结构分为（ A ）两大类。 A ．动态结构、静态结构 B ．顺序结构、链式结构 C ．线性结构、非线性结构 D ．初等结构、构造型结构 2、下面关于算法说法错误的是（ D ） A ．算法最终必须由计算机程序实现 B ．为解决某问题的算法同为该问题编写的程序含义是相同的 C ． 算法的可行性是指指令不能有二义性 D ．以上几个都是错误的 3、栈和队列的共同特点是( A )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 4、以下数据结构中，哪一个是线性结构（ D ）？ A ．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 5、下面关于线性表的叙述中，错误的是哪一个？（B） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 6、静态链表中指针表示的是（B）。 A．内存地址B．数组下标 C．表头地址 D．下一元素地址//所谓静态链表就是没有指针的，用下标模仿这个指针的功能的 7、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 8、下列各种排序算法中平均时间复杂度为O(n2)是（D）。 A．快速排序 B. 堆排序 C. 归并排序 D. 冒泡排序 9、设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择 （B）。 A. 小于等于m的最大奇数 B. 小于等于m的最大素数 C. 小于等于m的最大偶数 D. 小于等于m的最大合数 10、字符串的长度是指（C）。 A. 串中不同字符的个数 B. 串中不同字母的个数 C. 串中所含字符的个数 D. 串中不同数字的个数 11、设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为 （ D ）。 A. top=top+1; B. top=top-1; C. top->next=top; D. top=top->next; 12、二叉排序树可以得到一个从小到大的有序序列。( B ) A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 课程名称：结构力学【新】 一、单项选择题（本题共10道小题，每小题2分，共20分）在每小题列出的备选项中只有一个是符合题目要求的，错选、多选或未选均无分 1、如下图对称刚架所示，在反对称荷载作用下，正确的半边结构图号为（） A．图a B．图b C．图c D．图d 2、等直杆件AB的转动刚度S AB（） A．与B端支承条件及杆件刚度有关B．只与B端的支承条件有关 C．与A、B两端的支承条件有关D．只与A端支承条件有关 3、在单自由度体系受迫振动的动位移幅值计算公式y max=βy st中，y st是（） A．质量的重力所引起的静位移B．动荷载的幅值所引起的静位移 C．动荷载引起的动位移D．质量的重力和动荷载共同引起的静位移 4、变形体虚功原理的虚功方程中包含了力系与位移两套物理量，其中（） A．力系必须是虚拟的，位移是实际的B．位移必须是虚拟的，力系是实际的C．力系与位移都必须是虚拟的D．力系与位移都是实际的 5、等直杆件AB的弯矩传递系数C AB（） A．与B端支承条件及杆件刚度有关B．只与B端的支承条件有关 C．与A、B两端的支承条件有关D．只与A端支承条件有关 6、从位移法的计算方法来看，它（） A．只能用于超静定结构 B．主要用于超静定结构，但也可以用于静定结构 C．只能用于超静定结构中的刚架和连续梁 D．只能用于超静定次数小于3的结构 7、如下图两端固定的梁所示，设AB线刚度为i，当A、B两端截面同时发生单位转角时，则杆件A端的弯矩（） A．8i B．6i C．4i D．3i θA=1θB=1 A B 8、力法方程是沿基本未知量方向的（） A．力的平衡方程B．位移为零方程 C．位移协调方程D．力的平衡及位移为零方程 9、静定结构的内力计算与（） A．EI无关B．EI相对值有关C．I绝对值有关D．E无关，I有关 10、刚体体系与变形体体系虚功原理的虚功方程两者的区别在于（） A．前者用于求位移，后者用于求未知力 数据结构试卷（一） 一、单选题（每题2 分，共20分） 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在 676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二 分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O（1） B. O（n） C. O（1og2n） D. O（n2） 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K） =K %9作为散列函数，则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数 为__________个，树的深度为___________，树的度为_________。 4.后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式 为_______________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有_______个和________个。 7.AOV网是一种___________________的图。 8.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有 向完全图中，包含有________条边。 9.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元 素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持. 专升本《结构力学》 一、（共75题,共150分） 1. 图示梁剪力等于零的截面位置x距A点之值为( )。（2分） A.5a/6 B.6a/5 C.6a/7 D.7a/6 标准答案：D 2. 下列剪力图和弯矩图中的错误为( )。（2分） A.梁(A)图C截面剪力应连续，C截面弯矩应有突变；图 B.梁C截面弯矩应连续 B.图(A)梁B截面剪力不应为零，A截面弯矩不应为零；图B.梁C截面剪力应有突变，C截面弯矩应光滑连续 C.图(A)梁B截面剪力应为零，弯矩不为零；图B.AC段剪力应为曲线，弯矩图在AC 段有极值点 D.图(A)梁剪力在C截面应连续，弯矩在AC段的凹向应一至，图B.梁弯矩在C截面应连续 标准答案：A 3. 梁在集中力作用的截面处，它的内力图为( )。（2分） A.Q图有突变，M 图光滑连续 B.Q图有突变，M 图有转折 C.M图有突变，Q 图光滑连续 D.M图有突变，Q 图有转折 标准答案：B 4. 梁的剪力图和弯矩图如图所示，则梁上的荷载为( )。 （2分） A.AB段无荷载，B 截面有集中力 B.AB段有集中力，BC 段有均布力 C.AB段有均布力，B 截面有集中力偶 D.AB段有均布力，A 截面有集中力偶 标准答案：D 5. 用力矩分配法计算弹性结构时,放松结点的顺序________: （2分） A.对计算过程无影响,但对结果有影响; B.对计算过程有影响,但对结果无影响 C.对计算结果和过程均有影响; D.对计算结果和过程均无影响. 标准答案：B 6. 图示结构超静定次数为________: （2分） A.4 B.12 C.15 D.24 标准答案：C 7. 图示结构截面K的轴力值N k为________: （2分）A. B. C. D. 标准答案：C 东北农业大学网络教育学院 数据结构专升本作业题 作业题（一） 一、单项选择题 1. 从逻辑上可以把数据结构分为（C）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 2. 链表不具有的特点是（ B） A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 3.下面程序段的时间复杂度的量级为（D ）。 For(i=1;i<=n;i++) For(j=1;j<=I;j++) For(k=1;k<=j;k++) X=x+1; A．O(1) B．O(n) C．O(n2) D．O(n3) 4.在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（B ）个指针域的值。 A．2 B3 C．4 D．6 5、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（D）。 A．98 B．100 C．102 D．106 6、判定一个栈s（最多元素为m0）为空的条件是（ B ）。 A．s-〉top! =0 B．s-〉top= =0 C．s-〉top! =m0 D．s-〉top= =m0 7、循环队列用数组A[m]（下标从0到m-1）存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）。 A．（rear-front+m）%m B．rear-front+1 C．rear-front-1 D． rear-front 8、设有两个串S1与S2，求串S2在S1中首次出现位置的运算称作（）。 A．连接 B．求子串 C．模式匹配 D．判子串专升本试题(数据结构)
专升本《结构力学》_试卷_答案
山东07年专升本考试数据结构模拟试题.
数据结构专升本模拟题及答案
专升本《工程力学》_试卷_答案
专升本试题数据结构
结构力学专升本作业题参考答案
专升本《数据结构》_试卷_答案
专升本《结构力学》
专升本考试试题分析包括英语高数数据结构考试原题
专升本《数据结构》模拟题试卷
【良心出品】2013韩山师范学院专升本插班生考试《数据结构》课程试卷
土木工程【专升本】-结构力学试卷
(年)专升本十套数据结构(试题及标准答案)
专升本《结构力学》_试卷_答案
数据结构专升本模拟试题与参考答案
相关主题
文本预览