2012年河北工业大学数据结构与程序设计考研试题
- 格式：pdf
- 大小：601.97 KB
- 文档页数：3
文档推荐
-
河北工业大学软件工程期末复习页数:16
-
信息工程专业介绍页数:8
-
图论应用案例页数:21
-
河北工业大学软件工程期末复习页数:16
-
河北工业大学802数据结构07-12年真题页数:18
下载文档原格式
合集下载
数据结构真题2012年10月
数据结构真题2012年10月(总分：100.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.一个算法的时间耗费的数量级称为该算法的______（分数：2.00）A.效率B.难度C.可实现性D.时间复杂度√解析：[考点] 算法的时间复杂度的概念[解析] 一个算法的时间耗费的数量级称为该算法的时间复杂度。
2.顺序表便于______（分数：2.00）A.插入结点B.删除结点C.按值查找结点D.按序号查找结点√解析：[考点] 顺序表的特征[解析] 顺序表便于按序号查找结点。
3.设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是______（分数：2.00）A.p-＞next-＞next==headB.p-＞next==head √C.p-＞next-＞next==NULLD.p-＞next==NULL解析：[考点] 指针变量p指向尾结点的判定条件[解析] 单循环链表的指针变量p指向尾结点的判定条件是p-＞next==head。
4.设以数组A[0..m-1]存放循环队列，front指向队头元素，rear指向队尾元素的下一个位置，则当前队列中的元素个数为______（分数：2.00）A.(rear-front+m)%m √B.rear-front+1C.(front-rear+m)%mD.(rear-front)%m解析：[考点] 队列中元素个数的计算[解析] 队列中元素的个数为(rear-front+m)%m5.下列关于顺序栈的叙述中，正确的是______（分数：2.00）A.入栈操作需要判断栈满，出栈操作需要判断栈空√B.入栈操作不需要判断栈满，出栈操作需要判断栈空C.入栈操作需要判断栈满，出栈操作不需要判断栈空D.入栈操作不需要判断栈满，出栈操作不需要判断栈空解析：[考点] 顺序栈的性质的判断[解析] 入栈操作需要判断栈满，出栈操作需要判断栈空。
6.A是一个10×10的对称矩阵，若采用行优先的下三角压缩存储，第一个元素a 0，0的存储地址为1，每个元素占一个存储单元，则a 7，5的地址为______（分数：2.00）A.25B.26C.33D.34 √解析：[考点] 对称矩阵的元素的地址的计算[解析] 若对称矩阵采用下三角压缩存储，根据其地址的计算公式，可得到所求元素的地址。
河北工业大学2012年结构力学真题答案
河北工业大学2012年攻读硕士学位研究生入学考试试题参考答案（结构力学Ⅰ）一、是非题1. 02.×3. 04.×考点：1-3题考察静定结构、超静定结构的一般性质，4题考察组合结构的计算。
解析：1-3题请看下面编者语。
4题解答如下：AE 、EH 是梁式杆，AD 、DF 、FH 、CD 、GF 是链杆，故先求出支座反力、截断链杆DF 、解除E 点约束，取左半部分为研究对象,对E 点取距由0=∑E M 得：0223=⨯-⨯-⨯a F a P a P DF ，P F DF 2=，再根据D 结点的平衡可知：P N 21-=（求DF F 时也可以对A 点取距，根据对称性，E 结点的竖向力P 21，0=∑A M ，022/=⨯-⨯+⨯a F a P a P DF P F DF 2=）编者语：（1）关于静定结构、超静定结构的一般性质。
（2）关于组合结构的计算二、选择题1、B考点：影响线的应用中荷载最不利位置的确定。
解析：B R 的影响线如图所示：因必有一集中荷载在顶点，当48kN 力在顶点时，kN kN R B 682140148=⨯+⨯=，当40kN 力在顶点时，kN kN R B 721403248=⨯+⨯=，故kN R B 72=，选B 。
（选项中的C 选项分明是48kN+40kN=88kN 的结果，这只能是两力都加在B 上，而这是不可能的）。
编者语：关于荷载最不利位置的确定，有如下总结：最常见的、也是最重要的是上述2)、3)种情况，第5)种情况很少见，也可以说没有出过题目，故2)、3)情况必须要掌握，本题考察的是第2)种情况。
2.A考点：多跨静定梁的内力传递解析：当荷载作用于基本部分时，只有基本部分受力，附属部分不受力。
当荷载作用于附属部分时，则不仅附属部分受力，基本部分一般也受力。
本题中左边部分为主体结构，右边部分为附属结构，P力作用在主体结构上，右边附属结构不受力。
编者语：（1）有很多同学不明白，力作用在铰上，到底是作用在哪一边？我的回答是随便假设一边都可以算出相同的结果！现以此题来分析！由整体分析可知，水平力为零：当力作用在左边铰时：进一步解出：当力作用在右边铰时：进一步解出：故得出结论，对于集中荷载计算时，假设集中力作用在铰的任何一边都是可行的，故题目中直接把荷载加在铰上，但是要注意，当铰接处作用力偶时，应看清作用在铰的左侧还是右侧，力偶不能直接作用在铰上，只能作用在铰两侧的截面上。
河北工业大学数据结构与程序设计2010—2012年考研真题试题
A、 d,c,a,bB、
b,c,d,a C、
c,d,b,a D、
a,c,b,d
4、 若用一个大小为 6的数组来实现循环队列,且 当前 rear和 fr0矶 的值分别为 0和 3,当 从队列中删
除一个元素,再加入两个元素后,rear和 front的 值分别为多少?( )
A、 1和 5
B、 2和 4
C、 4和 2
11)装入下标范围为 0到 6的 Hash表 中,则该表中各关键字的次序为 (
)。
A、 72, 11, 37, 38, 56, 98, 48
B、 11, 48, 37, 38, 72, 98, 56
C、 98, 11, 37, 38, 72, 56, 48
D、 98, 56, 37, 38, 72, 11, 48
河北工业大学 2012年 攻读硕士学位研究生入学考试试题 [口 卷
科目名称 数据结构与程序设计
科目代码 80s 共 3 页
适用专业、领域
计算机技术 (专业学位)
注:所 有试题答案一律写在答题纸上,答 案写在试卷、草稿纸上-律 无效。
一、 填空题 (共 ⒛ 分,每空 2分 。答案一律写在答题纸上,否则无效。)
8 A、 B、 9 C、 10 D、 11
8、 高度为 6的满二叉树,总共具有的结点数是 ( )。
A、 15
B、 25
C、 20
D、 63
( 9、 树的后根遍历序列等同于该树对应的二叉树的
)
A、 先序序列 B、 中序序列 C、 后序序列
1O、 在一非空二叉树的中序遍历序列中,根结点的右边 ( )
A、 只有右子树上的所有结点
1、 写出下面稀疏矩阵的三元组表存储表示
2012年河北工业大学802数据结构考研试题 (1)
)长 度相等的两个串一定是相等的。
60分 )
四 、 简 答 题 (共
1、
(6分 )如 果关键字是主关键字的话 ,则 对一个无序的数据元素序列经按主关键字排序后得到的 (8分 )由 于线性表的链式存储结构可 以见缝插针的有效地利用存储 空间,所 以线性表的链式存
结果是否是唯一 的?为 什么 ?
2、
储结构的存储密度大于线性表的顺序存储结构 ,这 种说法对吗 ?为 什么 ?
2分 。答 案 一 律 写在 答 题 纸 上 ,否 则 无 效 。 )
的两个数据元素 ,在 物理存储上赋予 位置的一种存
线性表的顺序映象就是逻辑上
储分配方式 。
2、
我们把图中所有顶点加上遍历时经过的所有边构成的子图称为
。
3、
在直接插入排序 、希尔排序 、直接选择排序 、堆排序 、快速排序和基数排序中 ,需 要 内存量最 。
( )虽 说静态链表是用数组来实现的,但 对其进行插入和删除操作时,却 并不涉及数组元素
查找快。
4、
的移动问题 。
5、
6、
( (
(
)线 性表的顺序存储结构是一种随机存取的存储结构 。 )二 叉排序树的形态与记录的读入顺序无关 。
)Hash表 查找是一种不需 比较或需很少 比较的查找方法 。
7、
8、
(
4、
均匀的 Hash函 数 ?
5、
(10分 )请 问什么是稳定排序 ?和 非稳定排序相 比,它 有什么优点 ?为 什么说快速排序 、希尔
(6分 )二 叉排序树 T的 各元素值均不相同,请 问用什么有效方法 ,才 能按递增次序打印出元素
(10分 )什 么是队列的假溢出?通 常可以采用什么办法解决假溢出?
天勤论坛_2012年数据结构真题 (1)
图3
图4
该文档由天勤论坛（）整理，转载请注明出处
10. 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序下列排序方法
中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。
I．简单选择排序
II．希尔排序
III．快速排序
IV．堆排序
V．二路归并排序
图5
该文档由天勤论坛（）整理，转载请注明出处
【答案要点】 （1）算法的基本设计思想如下：
①分别求出 str1 和 str2 所指的两个链表的长度 m 和 n。 ②将两个链表表尾对其：令指针 p、q 分别指向 str1 和 str2 的头节点，若 m≥n，则使 p 指向链表中的第 m-n+1 个节点；若 m＜n，则使 q 指向链表中的第 n-m+1 个节点，即使指针 p、q 所指的节点到表尾的长度相等。 ③反复讲指针 p、q 同步后移，并判断他们是否指向同一节点（通过比较节点地址是否 相等，而不是比较节点值）。若 p、q 指向同一节点，则该节点即为所求的共同后缀的起始位 置。 （2）算法实现如下： typedef struct Node { char data; struct Node *next; }SNODE; SNODE *Findlist(SNODE *str1,SNODE *str2) { int m,n; SNODE *p,*q; m=Listlen(str1); n=Listlen(str2); for(p=str1;m>n;m--)
else return n*fact(n-1);
}
A．O(log2n)
B．O(n)
C．O(nlog2n) D．O(n2)
B。本算法是一个递归，设执行时间为 T(n)，则有：
2022年河北工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)
2022年河北工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下列说法不正确的是（）。
A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种：深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。
A.13B.33C.18D.403、以下与数据的存储结构无关的术语是（）。
A.循环队列B.链表C.哈希表D.栈4、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。
A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front5、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。
A.（rear+1）MOD n=frontB.rear=frontC.rear+1=frontD.（rear-1）MOD n=front6、下列选项中，不能构成折半查找中关键字比较序列的是（）。
A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4507、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。
A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝28、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。
A.CBEFDAB.FEDCBAC.CBEDFAD.不定9、设X是树T中的一个非根结点，B是T所对应的二叉树。
2012年河北省《数据结构》期末考试试题及答案理论考试试题及答案
A）2k B） 2k-1 C）k D） 2k
25、从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A.O(1) B.O(n)
C.O(1Ogzn) D.O(n2)
26、在平衡二叉树中插入一个结点后造成不平衡，设最低的不平衡结点为A，并已知A的左孩子平衡因子为0，右孩子平衡因子为1，则应该做（ ）型调整以使其平衡
D．顺序访问相邻结点更灵活
48、已知关键字序列为{66，82，25，51，98，108}，利用快速排序方法，以第一个元素为基准得到的一趟排序结果为
A．{25，51，66，82，98，108}
B．{25，51，66，98，82，108}
C．{51，25，66，108，98，82}
41、在数据结构中，与所使用的计算机无关的是数据的 A 结构。
A．逻辑 B．存储 C．逻辑和存储 D．物理
42、若一个栈以数组V[0．．n-1]存储，初始栈顶指针top为n，则x入栈的正确操作是
A．top=top+1；V[top]=x B．V[top]=x；top=top+1
A）ABDECFG B）DBEAFCG
C）DEBFGCA D）GFCEBDA
38、通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 B 。
A．数据元素具有同一特点
B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致
C．每个数据元素都一样
B．p->prior = s；p->prior->next = s；s->next = p；s->prior = p->prior
C．s->next = p；s->prior = p->prior；p->prior = s；p->prior->next = s
25、从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A.O(1) B.O(n)
C.O(1Ogzn) D.O(n2)
26、在平衡二叉树中插入一个结点后造成不平衡，设最低的不平衡结点为A，并已知A的左孩子平衡因子为0，右孩子平衡因子为1，则应该做（ ）型调整以使其平衡
D．顺序访问相邻结点更灵活
48、已知关键字序列为{66，82，25，51，98，108}，利用快速排序方法，以第一个元素为基准得到的一趟排序结果为
A．{25，51，66，82，98，108}
B．{25，51，66，98，82，108}
C．{51，25，66，108，98，82}
41、在数据结构中，与所使用的计算机无关的是数据的 A 结构。
A．逻辑 B．存储 C．逻辑和存储 D．物理
42、若一个栈以数组V[0．．n-1]存储，初始栈顶指针top为n，则x入栈的正确操作是
A．top=top+1；V[top]=x B．V[top]=x；top=top+1
A）ABDECFG B）DBEAFCG
C）DEBFGCA D）GFCEBDA
38、通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 B 。
A．数据元素具有同一特点
B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致
C．每个数据元素都一样
B．p->prior = s；p->prior->next = s；s->next = p；s->prior = p->prior
C．s->next = p；s->prior = p->prior；p->prior = s；p->prior->next = s
河北工程大学数据结构复习题
单项选择题1.数据的（B）包括集合、线性、树和图4种基本类型A．存储结构B．逻辑结构C．基本运算D．算法描述2.对一个长度为n的顺序表，在第i个元素（1≤i≤n+1）之前插入一个新元素时需向右移动（B）个元素。
A．n-i B．n-i+1 C．n-i-1 D．i3下面程序的时间复杂度为（C ）。
For(i=0;i<m;i++)For(j=0;j<n;j++)A[i][j]=i*j;A.O(m2)B. O(n2)C. O(n*m)D.O(n+m)4长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（C）。
若没说明在第几个位置插入，则其复杂度为DA．O(0) B．O(1) C．O(n) D．O(n2) 5.数据结构就是研究（D ）。
A．数据的逻辑结构B．数据的存储结构C．数据的逻辑结构和存储结构D．数据的逻辑结构、存储结构及其数据在运算上的实现6下面关于算法的说法，错误的是（D）。
A．算法最终必须由计算机程序实现B．为解决某问题的算法和为该问题编写的程序含义是相同的C．算法的可行性是指指令不能有二义性D．以上三种说法都错误7线性表L=（a1，a2 ，……an，）下列说法正确的是（D ）。
A．每个元素都有一个直接前驱和一个直接后继B．线性表中至少要有一个元素C．表中所有元素的排列顺序必须是由小到大或由大到小D．除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和一个直接后继8．下面关于线性表叙述错误的是（ B ）。
A．线性表采用顺序存储，必须占用一段地址连续的单元B．线性表采用顺序存储，便于进行插入和删除操作C．线性表采用链式存储，不必占用一段地址连续的单元D．线性表采用链式存储，便于进行插入和删除操作9用链表表示线性表的优点是（C）A．便于随机存取B．存储空间比顺序存储方式少C．便于插入和删除D．数据元素的存储顺序与逻辑顺序相同10若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（ D ）存储方式最节省时间。
河北工业大学-考研资料-数据结构--习题1答案
一填空1.衡量算法效率的两个重要指标称为算法的______时间复杂度_和___空间复杂度2. 一个算法应具有有穷性，确定性，可行性，输入和输出这五个特性。
3. 线性表的长度是指___表中元素的个数___。
4. 在线性表的顺序存储中，元素之间的逻辑关系是通过元素存储的相对位置决定的；在线性表的链接存储中，元素之间的逻辑关系是通过相关元素的存储位置决定的。
5 在双向链表中，每个结点包含两个指针域，一个指向其直接前趋结点，另一个指向其直接后继结点。
二、判断题1．线性表的逻辑顺序与存储顺序总是一致的。
(FALSE)2．顺序存储的线性表可以按序号随机存取。
(TRUE)3．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。
（FALSE）4．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。
（TRUE）5．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。
（TRUE）6．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。
（TRUE）三、单选题(请从下列A，B，C，D选项中选择一项)1．线性表是( ) 。
(A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空；(C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。
答：A2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。
插入一个元素时平均要移动表中的（）个元素。
(A) n/2 (B)（n+1）/2 (C) (n –1)/2 (D) n答：A3．线性表采用链式存储时，其地址( ) 。
(A) 必须是连续的；(B) 部分地址必须是连续的；(C) 一定是不连续的；(D) 连续与否均可以。
答：D4．用链表表示线性表的优点是（）。
(A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和删除(D)数据元素的物理顺序与逻辑顺序相同答：C5. 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。
真题_2012年_数据结构
参考答案：B
5.对有n个顶点、e条边且使用邻接表存储的有向图进行广度 优先遍历,其算法时间复杂度是 A. O(n) B. O(e) C. O(n+e) D. O(n*e)
参考答案：C
6.若用邻接矩阵存储有向图,矩阵中主对角线以下的元素均为 零,则关于该图拓扑序列的结论是 A.存在，且唯一 B.存在，且不唯一 C.存在，可能不唯一 D.无法确定是否存在
3.若一棵二叉树的前序遍历序列为 a,e,b,d,c,后序遍历序列为 b,c,d,e,a,则根结点的孩子结点
A.只有 e B.有 e、 b C.有 e、 c D.无法确定
参考答案：A
4.若平衡二叉树的高度为6,且所有非叶结点的平衡因子均为 1, 则该平衡二叉树的结点总数为 A. 12 B. 20 C. 32 D.33
参考答案：C
8. 下列关于最小生成树的叙述中,正确的是 I. 最小生成树的代价唯一 Ⅱ. 所有权值最小的边一定会出现在所有的最小生成树中 Ⅲ.使用普里姆 (Prim)算法从不同顶点开始得到的最小生成树一 定相同 IV. 使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生 成树总不相同 A. 仅 I B. 仅 Ⅱ C. 仅 I、 Ⅲ D. 仅 Ⅱ、Ⅳ
参考答案：C
7. 对如下有向带权图,若采用迪杰斯特拉 (Dijkstra) 算法求从源点a到其他各顶点的最短路径,则得到 的第一条最短路径的目标顶点是b,第二条最短路 径的目标顶点是 c,后续得到的其余各最短路径的 目标顶点依次是 A. d,e,f B. e,d,f C. f,d,e D. f,e,d
2012年全国硕士研究生入学统一考 试计算机学科专业基础综合试卷
数据结构部分
一、单项选择题：1~40小题。每小题2分，共80分。 在每小题给出的四个选项中，请选出一项最符合题 目要求的。