专升本⼗套-数据结构（试题及答案）
数据结构试卷（⼀）
⼀、单选题（每题2分，共20分）
1.栈与队列得共同特点就是( )。
A、只允许在端点处插⼊与删除元素
Ｂ、都就是先进后出
C、都就是先进先出
D、没有共同点
2.⽤链接⽅式存储得队列，在进⾏插⼊运算时（）、
A、仅修改头指针
B、头、尾指针都要修改
C、仅修改尾指针Ｄ、头、尾指针可能都要修改
3.以下数据结构中哪⼀个就是⾮线性结构？( )
Ａ、队列Ｂ、栈C、线性表Ｄ、⼆叉树
4.设有⼀个⼆维数组A[m］［n］，假设Ａ［0］[０］存放位置在644（10）,A［２］［2］存
放位置在６76（１0），每个元素占⼀个空间，问A[3］[3](10)存放在什么位置？脚注(１0）表⽰⽤10进制表⽰。
A.6８8 B．６７8 C.6９2D．69６
二叉树的遍历及应用实验报告5.树最适合⽤来表⽰（)。
Ａ、有序数据元素B、⽆序数据元素
C、元素之间具有分⽀层次关系得数据
D、元素之间⽆联系得数据
6.⼆叉树得第k层得结点数最多为( )、
Ａ。２ｋ—１ B、2K+1 C、2K-1 D、 2k-１
7.若有１8个元素得有序表存放在⼀维数组A［19]中，第⼀个元素放A［１]中，现进
⾏⼆分查，则查Ａ［3］得⽐较序列得下标依次为( )
A、1,2,3 ??Ｂ、9，5，2，３
C、9，５,3
D、9,4，2，3
8.对ｎ个记录得⽂件进⾏快速排序，所需要得辅助存储空间⼤致为
A、Ｏ(1）Ｂ、O（ｎ） C、 O（1og2n) D、 O(n２)
9.对于线性表(7,34,5５，25,64，４6，20,10）进⾏散列存储时，若选⽤H（K）=K %9
作为散列函数，则散列地址为1得元素有（）个，
A。1 B．2 C．3 D．4
10.设有6个结点得⽆向图，该图⾄少应有（)条边才能确保就是⼀个连通图。
A、5
B、6
C、7 Ｄ、8
⼆、填空题（每空1分，共26分）
1.通常从四个⽅⾯评价算法得质量：__＿＿＿_＿__、_________、______＿__与____＿_
＿__.
2.⼀个算法得时间复杂度为（n３＋ｎ2ｌog２n+14n）／n２，其数量级表⽰为________.
3.假定⼀棵树得⼴义表表⽰为A(C，Ｄ（E,F，G），H(I，J）），则树中所含得结点数为__
＿_______个，树得深度为________＿__，树得度为__＿______。
4.后缀算式9 2 3 +— 1０ 2 ／—得值为_______＿＿_.中缀算式（３+4X)－2Y/3对应得
后缀算式为__＿___＿＿____＿_＿_＿____＿___＿__＿＿＿。
5.若⽤链表存储⼀棵⼆叉树时，每个结点除数据域外，还有指向左孩⼦与右孩⼦得两个指
针。在这种存储结构中,n个结点得⼆叉树共有＿____＿__个指针域，其中有______＿_个指针域就是存放了地址，有______＿___＿_____个指针就是空指针。
6.对于⼀个具有n个顶点与e条边得有向图与⽆向图，在其对应得邻接表中，所含边结点
分别有＿____＿_个与_＿__＿＿_＿个。
7.AOV⽹就是⼀种＿______＿_____＿_＿___得图。
8.在⼀个具有n个顶点得⽆向完全图中，包含有__＿_＿___条边，在⼀个具有n个顶点得
有向完全图中，包含有___＿___＿条边。
9.假定⼀个线性表为（12，23，７４,５５，６3，４0)，若按Keｙ％4条件进⾏划分，
使得同⼀余数得元素成为⼀个⼦表，则得到得四个⼦表分别为＿__＿_＿＿____＿
______＿__＿_＿____、＿____＿＿_＿＿_＿______＿、＿__＿__＿______＿____＿_
＿＿_与＿＿___＿＿＿___＿_＿＿___＿＿＿__＿__。
10.向⼀棵B_树插⼊元素得过程中，若最终引起树根结点得分裂，则新树⽐原树得⾼度
_______＿_＿_。
11.在堆排序得过程中，对任⼀分⽀结点进⾏筛运算得时间复杂度为___＿__＿_，整个堆排序
过程得时间复杂度为__＿＿__＿_。
12.在快速排序、堆排序、归并排序中，_＿_______排序就是稳定得.
三、计算题（每题６分，共２4分)
1.在如下数组A中链接存储了⼀个线性表，表头指针为Ａ［0]、ｎext，试写出该线性表.
Ａ0 1 2 3 4 5 6 7
data 6
3 5 7 2 ０
4 1
nex
ｔ
2.
3.已知⼀个图得顶点集V与边集E分别为：V={1，2，
3,４，5，6,７}；
E=｛(1，２)3，（1，3）5，(1，4）８，（２，５）
１0,（２,3）6，（３，4）1５,
（３，5)1２,（3,6)９，（４,６）4，（4，７）20，（5,6）
18,（6,7）25｝；
⽤克鲁斯卡尔算法得到最⼩⽣成树，试写出在最⼩⽣成树中依次得到得各条边。
4.画出向⼩根堆中加⼊数据4，2,５, 8，3时，每加⼊⼀个数据后堆得变化。
四、阅读算法（每题7分，共1４分)
1.ＬｉnｋLｉsｔmｙｎｏｔe（LinkLiｓt L)
｛/／Ｌ就是不带头结点得单链表得头指针
if(L&＆Ｌ—〉next）{
q＝L;L=Ｌ—〉next;p=L；
S1: whｉle（p->ｎeｘt）ｐ=ｐ—>next;
S２：p－〉ｎeｘt=q；q—〉ｎexｔ＝ＮULＬ;
}
ｒeturn L；
}
请回答下列问题：
(1)说明语句Ｓ1得功能;
（2）说明语句组S2得功能;
（３）设链表表⽰得线性表为(ａ1，a2，…,aｎ)，写出算法执⾏后得返回值所表⽰得线性表.
2.voｉｄAＢＣ（BTNｏde＊ＢＴ)
｛
if ＢＴ{
AＢC（BＴ－〉leｆt);
ABC（BT—>rｉght);
ｃout＜＜BＴ—>dａta〈〈’ ’；
｝
｝
该算法得功能就是:
五、算法填空（共8分）
⼆叉搜索树得查—-递归算法:
ｂoｏl Finｄ（ＢＴrｅeＮode＊ BＳT，ElemＴyｐe& itｅm)
｛
iｆ (BSＴ=＝NＵLL）
rｅtｕrｎ falsｅ; ／／查失败
eｌｓe ｛
if (itｅｍ＝＝BST—>daｔa)｛
iteｍ=BSＴ-〉ｄａta;//查成功
ｒeturn ..____＿_＿___＿；｝
elｓe ｉf(itｅm〈BSＴ—>ｄａta）
rｅｔｕrn Finｄ（__________＿___，iｔｅm）；
eｌse reｔurｎＦinｄ（____＿__＿＿___＿＿_,iｔem）；
｝//iｆ
}
六、编写算法（共8分）
统计出单链表HＬ中结点得值等于给定值X得结点数。
ｉnｔ CｏｕntX(LNｏde＊ HＬ,ＥlemTｙpe x)
数据结构试卷(⼆)
⼀、选择题（24分）
１.下⾯关于线性表得叙述错误得就是( )。
（Ａ) 线性表采⽤顺序存储必须占⽤⼀⽚连续得存储空间?
(B）线性表采⽤链式存储不必占⽤⼀⽚连续得存储空间
（Ｃ) 线性表采⽤链式存储便于插⼊与删除操作得实现
（Ｄ）线性表采⽤顺序存储便于插⼊与删除操作得实现
2。设哈夫曼树中得叶⼦结点总数为m，若⽤⼆叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。（Ａ）2m－１(B）２m (C）２m+１?（D) ４m
3.设顺序循环队列Q［0:Ｍ—1]得头指针与尾指针分别为F与R，头指针Ｆ总就是指向队头元
素得前⼀位置，尾指针R总就是指向队尾元素得当前位置，则该循环队列中得元素个数为（）。
（Ａ） R—Ｆ（B）F－R?（C） (Ｒ－F+M)％Ｍ?（D) （F-R+Ｍ)%Ｍ
４.设某棵⼆叉树得中序遍历序列为AＢCD，前序遍历序列为CＡBD，则后序遍历该⼆叉树得到序列为(）。(Ａ）ＢADＣ(B) ＢCDＡ(Ｃ） CＤAB?(D） CBDA
５。设某完全⽆向图中有ｎ个顶点，则该完全⽆向图中有（ )条边。
（A) n（n—１）／2?（B） n（n-１）?（C) n2?(D) n2—1
6．设某棵⼆叉树中有2０00个结点，则该⼆叉树得最⼩⾼度为（）.
（A) 9 （Ｂ） 10?(C) １１(Ｄ) 12
7.设某有向图中有ｎ个顶点，则该有向图对应得邻接表中有( )个表头结点.
（A） n-１?（B）ｎ?(C) n+1?(Ｄ) ２n－1
8。设⼀组初始记录关键字序列(５,２,6，3，8)，以第⼀个记录关键字5为基准进⾏⼀趟快速排序得结果为（ )。
(Ａ）２，3，5，8，6 ?(B) 3，2，5,8，6
(C）3，２，５,6,8?(D）２,3,6,5,8
⼆、填空题（24分）
1.为了能有效地应⽤HAＳＨ查技术，必须解决得两个问题就是_＿_＿_＿___＿＿___＿
_＿___与______＿__＿__＿__＿_＿＿_______。
2.下⾯程序段得功能实现数据x进栈，要求在下划线处填上正确得语句.
typeｄeｆstrucｔ｛int s［1０0］；ｉnt top;｝sqｓtack；
ｖｏid pｕsh(sqstａck ＆sｔａck，int x)
{
if （staｃk、toｐ==m－１）priｎtf(“ovｅrfｌow”）;
eｌｓe｛__＿＿＿__＿________＿___；_＿___＿__＿__＿____＿；｝}
3.中序遍历⼆叉排序树所得到得序列就是___＿_______序列（填有序或⽆序)。
4.快速排序得最坏时间复杂度为__________＿，平均时间复杂度为________＿_.
5.设某棵⼆叉树中度数为０得结点数为N0，度数为1得结点数为N１，则该⼆叉树中度数
为2得结点数为＿___＿____；若采⽤⼆叉链表作为该⼆叉树得存储结构，则该⼆叉树中共有__＿____个空指针域。
6.设某⽆向图中顶点数与边数分别为n与e，所有顶点得度数之与为d，则e=_______.
7.设⼀组初始记录关键字序列为（55，63，44,38，７5,80,31,５6），则利⽤筛选法建⽴
得初始堆为__＿__＿＿________＿_＿＿________。
8。已知⼀有向图得邻接表存储结构如下：从顶点1出发，DFS遍历得输出序列就是
,BＦS遍历得输出序列就是
三、应⽤题(3６分）
1．设⼀组初始记录关键字序列为（4５,８0，48，４0，2２，78），则分别给出第4趟简单选择排序与第4趟直接插⼊排序后得结果。
2．设指针变量p指向双向链表中结点A，指针变量q指向被插⼊结点B，要求给出在结点A 得后⾯插⼊结点B得操作序列（设双向链表中结点得两个指针域分别为llink与ｒliｎk）。
3．设⼀组有序得记录关键字序列为(１3，1８，24,35，47，50，62，８３,90)，查⽅法⽤⼆分查，要求计算出查关键字62时得⽐较次数并计算出查成功时得平均查长度.
4．设⼀棵树T中边得集合为｛（Ａ，B），(A,C),（A,Ｄ），(B，E)，(C，F)，(C，G）｝，要求⽤孩⼦兄弟表⽰法(⼆叉链表）表⽰出该树得存储结构并将该树转化成对应得⼆叉树。5．设有⽆向图Ｇ，要求给出⽤普⾥姆算法构造最⼩⽣成树所⾛过得边得集合.
6．设有⼀组初始记录关键字为(45，８０，48,4０，22,７8)，要求构造⼀棵⼆叉排序树并给出构造过程。
四、算法设计题(16分）
1．设有⼀组初始记录关键字序列（K1,K2，…，Kｎ），要求设计⼀个算法能够在O（n)得时间复杂度内将线性表划分成两部分，其中左半部分得每个关键字均⼩于Kｉ，右半部分得每个关键字均⼤于等于Ｋi。
2．设有两个集合A与集合B，要求设计⽣成集合Ｃ＝A∩B得算法，其中集合A、B与Ｃ⽤链式存储结构表⽰。
数据结构试卷(三）
⼀、选择题(每题1分，共２０分）

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。