数据结构每日一题 2020 Sep#
目录#
1. Week 3#
1.1. Tue#
若二维数组arr[1..M，1..N]的首地址为base，数组元素按列存储且每个元素占用K个存储单元，则元素arr[i，j]在该数组空间的地址为 [厦门大学-903-2015] A．base+((i-1)M+j-1)K B．base+((i-1)N+j-1)K C．base+((j-1)M+i-1)K D．base+((j-1)N+i-1)K
答案
答案：C解析：二维数组arr[1..M，1..N]的元素可以按行存储，也可以按列存储。按列存储时，元素的排列次序为，先是第一列的所有元素，然后是第二列的所有元素，最后是第N列的所有元素。每一列的元素则按行号从小到大依次排列。因此，对于元素arr[i，j]，其存储位置如下计算：先计算其前面j-1列上的元素总数，为(j-1)*M，然后计算第j列上排列在arr[i，j]之前的元素数目，为i-1，因此arr[i，j]的地址为base+((j-1)*M+i-1)*K。
1.2. Wed#
数组Q［n］用来表示一个循环队列,f为当前队列头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数小于n,计算队列中元素个数的公式为 [浙江理工大学-991-2011]
A．r－f
B．（n＋f－r）% n
C．n＋r－f
D．（n＋r－f）% n
答案
答案：D解析：当r>f时，个数x = r - f ，当r < f时，x = n + r - f ，二者可以统一为D选项。
2. Week 4#
2.1. Wed#
设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15,38,61,84共四个，现要将关键字为26的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是 [武汉科技大学-856-2013]
A．8
B．3
C．2
D．9
答案
答案：B解析：H(15)=15%11=4
H(38)=38%11 = 5
H(61)=61%11 = 6
H(84)=84%11 = 7
H(26)=26%11=4
关键字26的结点和关键字为15 的结点都放在哈希表4的位置，产生冲突
利用二次探测再散列法公式H(key)=（key+dii）%11 dii=1^2 ，-(1^2)，2^2，-(2^2).....
当dii取1^2时：
H(26)=（26+1^2）%11 = 5
和 H(38)=38%11 =5 冲突
当dii取-1^2时：H(26)=（26-(1^2)）%11 = 3 不与其他关键字的哈希地址冲突，故将关键字26的结点放在表3位置。
2.2. Sun#
在有N个叶子节点的哈夫曼树中，其节点总数为 [郑州大学]
A. 不确定
B. 2N-1
C. 2N+1
D. 2N
答案
答案：B解析：哈弗曼树也是二叉树，而且树中只有叶子结点跟度为2的结点，由二叉树的性质可得：度为2的结点数量等于叶子结点数量-1，因此结点总数为n+n-1。